Optimization problems and the polynomial hierarchy. (English) Zbl 0459.68016


68Q25 Analysis of algorithms and problem complexity
68R99 Discrete mathematics in relation to computer science
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Aho, A.; Hopcroft, J.; Ullman, J., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0326.68005
[2] Baker, T.; Gill, J.; Solovoy, R., Relativizations of the P=NP? question, SIAM J. Comput., 4 (1975)
[3] Baker, T. P.; Selman, A. L., A second step toward the polynomial hierarchy, Theoret. Comput. Sci., 8, 177-187 (1979) · Zbl 0397.03023
[4] Book, R. V., Translational lemmas, polynomial time, and (log \(n)^i\)-space, Theoret. Comput. Sci., 1, 215-226 (1976) · Zbl 0326.68030
[5] Cook, S., The complexity of theorem proving procedures, Proc. 3rd Annual ACM Symposium on Theory of Computing, 151-158 (1971) · Zbl 0253.68020
[6] Garey, M. R.; Johnson, D. S., Computers and Intractability—A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[7] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. J., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237-267 (1976) · Zbl 0338.05120
[8] Hartmanis, J.; Hopcroft, J., Independence results in computer science, ACM SIGACT News, 8, 13-23 (1976)
[9] Karp, R. M., Reducibility along combinatorial problems, (Miller; Thatcher, Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-104 · Zbl 1467.68065
[10] Ladner, R. E.; Lynch, N. A.; Selman, A. L., Comparison of polynomial time reducibilities, Theoret. Comput. Sci., 1, 103-123 (1975) · Zbl 0321.68039
[11] Leggett, E. W., Tools and techniques for classifying NP-hard problems, (Ph.D. Thesis (1977), Ohio State University: Ohio State University Columbus)
[12] Meyer, A.; Stockmeyer, L. J., The equivalence for regular expression with squaring requires exponential spare, Proc. 13th Annual Symposium on Switching and Automata Theory, 125-129 (1972)
[13] Stockmeyer, L. J.; Meyer, A., Word problems requiring exponential time, Proc. 5th Annual ACM Symposium on Theory of Computing, 1-9 (1973) · Zbl 0359.68050
[14] Sahni, S., Computationally related problems, SIAM J. Comput., 3, 262-279 (1974) · Zbl 0272.68040
[15] Sahni, S.; Gonzalez, T., P-complete approximation problems, J. ACM, 23, 55-565 (1976) · Zbl 0348.90152
[16] Selman, A. L., Polynomial time enumeration reducibility, SIAM J. Comput., 7, 440-457 (1978) · Zbl 0386.68055
[17] Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1976) · Zbl 0353.02024
[18] Wrathall, C., Complete sets and the polynomial-time hierarchy, Theoret. Comput. Sci., 3, 23-33 (1976) · Zbl 0366.02031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.