## Abstract

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 ∑_{P}^{2}-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 ∑_{P}^{2}-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 ∑_{P}^{2}-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 R_{NP} of all concept classes whose membership problems are in NP.

Original language | English |
---|---|

Pages (from-to) | 269-310 |

Number of pages | 42 |

Journal | Computational Complexity |

Volume | 1 |

Issue number | 3 |

DOIs | |

State | Published - 1 Sep 1991 |

## Keywords

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