Complexity of the consistency problem for certain Post classes
I Shmulevich1, M Gabbouj, J Astola
1Int. Center for Signal Process., Tampere Univ. of Technol.
Abstract:
The complexity of the consistency problem for several important classes of Boolean functions is analyzed. The classes of functions under investigation are those which are closed under function composition or superposition. Several of these so-called Post classes are considered within the context of machine learning with an application to breast cancer diagnosis. The considered Post classes furnish a user-selectable measure of reliability. It is shown that for realistic situations which may arise in practice, the consistency problem for these classes of functions is polynomial-time solvable.
Related Concept Videos
Constraints and Statical Determinacy
Cognitive Dissonance
Stability of structures
Continuity for Functions of Multiple Variables
Second Uniqueness Theorem
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the surface...
Stability of Equilibrium Configuration
A stable equilibrium occurs when a system tends to return to its original position when given a small displacement, and the potential energy is at its minimum. An example of a stable equilibrium is when a cantilever beam is fixed at one end and a weight is attached to the other end. If the weight...
