Complexity of the consistency problem for certain post classes

I. Shmulevich; M. Gabbouj; J. Astola

doi:10.1109/3477.915348

Complexity of the consistency problem for certain post classes

I. Shmulevich
, M. Gabbouj
, J. Astola

Research output: Contribution to journal › Letter › peer-review

4 Scopus citations

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.

Original language	English
Pages (from-to)	251-253
Number of pages	3
Journal	IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume	31
Issue number	2
DOIs	https://doi.org/10.1109/3477.915348
State	Published - Apr 2001
Externally published	Yes

Keywords

Computational complexity
Computational learning theory
Consistency problem
Monotone Boolean function
Post class

Access to Document

10.1109/3477.915348

Cite this

@article{a1983593520b4d7dadfe899896251a01,

title = "Complexity of the consistency problem for certain post classes",

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 = "Computational complexity, Computational learning theory, Consistency problem, Monotone Boolean function, Post class",

author = "I. Shmulevich and M. Gabbouj and J. Astola",

year = "2001",

month = apr,

doi = "10.1109/3477.915348",

language = "English",

volume = "31",

pages = "251--253",

journal = "IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics",

issn = "1083-4419",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "2",

}

TY - JOUR

T1 - Complexity of the consistency problem for certain post classes

AU - Shmulevich, I.

AU - Gabbouj, M.

AU - Astola, J.

PY - 2001/4

Y1 - 2001/4

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Computational learning theory

KW - Consistency problem

KW - Monotone Boolean function

KW - Post class

UR - https://www.scopus.com/pages/publications/0035309535

U2 - 10.1109/3477.915348

DO - 10.1109/3477.915348

M3 - Letter

AN - SCOPUS:0035309535

SN - 1083-4419

VL - 31

SP - 251

EP - 253

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

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

IS - 2

ER -

Complexity of the consistency problem for certain post classes

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this