Three ∑P2-complete problems in computational learning theory

Ker I. Ko*, Wen-Guey Tzeng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


The consistency problem associated with a concept class C is to determine, given two sets A and B of examples, whether there exists a concept c in C such that each x in A is a positive example of c and each y in B is a negative example of c. We explore in this paper the following intuition: for a concept class C, if the membership problem of determining whether a given example is positive for a concept is NP-complete, then the corresponding consistency problem is likely to be ∑P2-complete. To support this intuition, we prove that the following three consistency problems for concept classes of patterns, graphs and generalized Boolean formulas, whose membership problems are known to be NP-complete, are ∑P2-complete: (a) given two sets A and B of strings, determine whether there exists a pattern p such that every string in A is in the language L(p) and every string in B is not in the language L(p); (b) given two sets A and B of graphs, determine whether there exists a graph G such that every graph in A is isomorphic to a subgraph of G and every graph in B is not isomorphic to any subgraph of G; and (c) given two sets A and B of Boolean formulas, determine whether there exists a 3-CNF Boolean formula θ such that for every φ{symbol} ∈A, θ ∧ φ{symbol} is satisfiable and for every Ψ ∈B, θ ∧ Ψ is not satisfiable. These results suggest that consistendy problems in machine learning are natural candidates for ∑P2-complete problems if the corresponding membership problems are known to be NP-complete. In addition, we prove that the corresponding prediction problems for concept classes of polynomial-time nondeterministic Turing machines, nondeterministic Boolean circuits, generalized Boolean formulas, patterns and graphs are prediction-complete for the class RNP of all concept classes whose membership problems are in NP.

Original languageEnglish
Pages (from-to)269-310
Number of pages42
JournalComputational Complexity
Issue number3
StatePublished - 1 Sep 1991


  • Computational learning theory
  • Subject classifications: 68Q15, 68T05
  • graph reconstruction
  • pattern languages
  • ∑-completeness


Dive into the research topics of 'Three ∑<sub>P</sub><sup>2</sup>-complete problems in computational learning theory'. Together they form a unique fingerprint.

Cite this