Abstract
The consistency problem associated with a concept classC is to determine, given two setsA andB of examples, whether there exists a conceptc inC such that eachx inA is a positive example ofc and eachy inB is a negative example ofc. We explore in this paper the following intuition: for a concept classC, if the membership problem of determining whether a given example is positive for a concept isNP-complete, then the corresponding consistency problem is likely to be ∑ 2 P -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 beNP-complete, are ∑ 2 P -complete: (a) given two setsA andB of strings, determine whether there exists a patternp such that every string inA is in the languageL(p) and every string inB is not in the languageL(p); (b) given two setsA andB of graphs, determine whether there exists a graphG such that every graph inA is isomorphic to a subgraph ofG and every graph inB is not isomorphic to any subgraph ofG; and (c) given two setsA andB of Boolean formulas, determine whether there exists a 3-CNF Boolean formula θ such that for every ϕ ∈A, θ ∧ ϕ is satisfiable and for every Ψ ∈B, θ ∧ Ψ is not satisfiable. These results suggest that consistendy problems in machine learning are natural candidates for ∑ 2 P -complete problems if the corresponding membership problems are known to beNP-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 classR NP of all concept classes whose membership problems are inNP.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. Angluin, Finding patterns common to a set of strings,J. Comput. System Sci.,21 (1980), 46–62.
D. Angluin, Queries and concept learning,Mach. Learn.,2 (1987), 319–342.
A. Blumer, A. Ehrenfeucht, D. Haussler andM. Warmuth, Learnability and the Vapnik-Chervonenkis dimension,J Assoc. Comput. Mach.,36 (1989), 929–965.
R. Board and L. Pitt, On the necessity of Occam algorithms, inProc. 22nd Ann. ACM Symp. Theory of Computing, 1990, 54–63.
S.A. Cook, The complexity of theory-proving procedures, inProc. 3rd Ann. ACM Symp. Theory of Computing, 1971, 151–158.
M.R. Garey andD.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979.
F. Harary,Graph Theory, Addison-Wesley, Reading, MA., 1969.
D. Haussler, M. Kearns, N. Littlestone andM.K. Warmuth, Equivalence of models for polynomial learnability, inProc. 1st Workshop Computational Learning Theory, Morgan Kaufmann, San Mateo, CA., 1988, 42–55.
D. Haussler, N. Littlestone and M.K. Warmuth, Predicting {0,1}-functions on randomly drawn points, inProc. 29th Ann. IEEE Symp. Foundations of Computer Science, 1988, 100–109.
T. Huynh, Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is ∑ 2 P -complete, inProc. 23rd Ann. IEEE Sympo. Foundations of Computer Science, 1982, 21–31.
R. Karp and R. Lipton, Some connections between nonuniform and uniform complexity classes, inProc. 12th Ann. ACM Symp. Thoery of Computing, 1980, 302–309.
M. Kearns andL. Pitt, A polynomial time algorithm for learningk-variable pattern languages from examples, inProceedings of the 2nd Workshop on Computational Learning Theory, Morgan Kaufmann, San Mateo, CA., 1989, 57–71.
K. Ko andC. Hua, A note on the two-variable pattern-finding problem,J. Comput. System Sci.,34 (1987), 75–86.
K. Ko, A. Marron andW. Tzeng, Learning string patterns and tree patterns from examples, inProc. 7th Intern. Conf. Machine Learning, Morgan Kaufmann, San Mateo, CA., 1990, 384–391.
A.R. Meyer and L.J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, inProc. 13th IEEE Symposium on Switching and Automata Theory, 1972, 125–129.
L. Pitt andL.G. Valiant, Computational limitations on learning from examples.J. Assoc. Comput. Mach.,35 (1988), 965–984.
L. Pitt andM.K. Warmuth, Prediction-preserving reducibility,J. Comput. System Sci.,41 (1990), 430–467.
Y. Sagiv andM. Yannakakis, Equivalences among relational expressions with the union and difference operators,J. Assoc. Comput. Mach.,27 (1980), 633–655.
R.E. Schapire, The strength of weak learnability,Mach. Learn.,5 (1990), 197–227.
R.E. Schapire, Pattern languages are not learnable, inProc. 3rd Workshop Computational Learning Theory, Morgan Kaufmann, San Mateo, CA., 1990, 122–129.
L.J. Stockmeyer and A.R. Meyer, Word problems requiring exponential time, inProc. 5th Ann. ACM Symp Theory of Computing, 1973, 1–9.
L.J. Stockmeyer, The polynomial-time hierarchy,Theoret. Comput. Sci.,3 (1977), 1–22.
L.G. Valiant, A theory of the learnable,Comm. Assoc. Comput. Mach.,27 (1984), 1134–1142.
K.W. Wagner, The complexity of combinatorial problems with succinct input representation,Acta Inform.,23 (1986), 325–356.
C. Wrathall, Complete sets and the polynomial-time hierarchy,Theoret. Comput. Sci.,3 (1977), 23–33.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ko, KI., Tzeng, WG. Three ∑ 2 P -complete problems in computational learning theory. Comput Complexity 1, 269–310 (1991). https://doi.org/10.1007/BF01200064
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01200064