Complexity of the consistency problem for certain Post classes

Author

Shmulevich, Ilya ; Gabbouj, Moncef ; Astola, Jaakko

Author_Institution

Int. Center for Signal Process., Tampere Univ. of Technol., Finland

Volume

31

Issue

2

fYear

2001

fDate

4/1/2001 12:00:00 AM

Firstpage

251

Lastpage

253

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

Keywords

Boolean functions; computational complexity; learning (artificial intelligence); Boolean functions; Post class; Post classes; complexity; computational complexity; computational learning theory; consistency problem; function composition; monotone Boolean function; polynomial-time solvable; superposition; Algebra; Boolean functions; Breast cancer; Control system synthesis; Machine learning; Manufacturing processes; Medical diagnosis; Polynomials; Signal analysis; Signal processing algorithms;

fLanguage

English

Journal_Title

Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on

Publisher

ieee

ISSN

1083-4419

Type

jour

DOI

10.1109/3477.915348

Filename

915348