Complexity of the consistency problem for certain Post classes
Ilya Shmulevich, Moncef Gabbouj, Jaakko T. Astola · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · 2001
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.