The polynomial-time hierarchy. (English) Zbl 0353.02024


03D55 Hierarchies of computability and definability
03D20 Recursive functions and relations, subrecursive hierarchies
03D40 Word problems, etc. in computability and recursion theory
03D10 Turing machines and related notions
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
Full Text: DOI


[1] Ackermann, W., Solvable cases of the decision problem, (1954), North-Holland Amsterdam · Zbl 0056.24505
[2] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0207.01701
[3] Aho, A.V.; Ullman, J.D., The theory of parsing, translation, and compiling, vol. I: parsing, (1972), Prentice-Hall Englewood Cliffs, N.J · Zbl 0264.68032
[4] Baker, T.; Gill, J.; Solovay, R., Relativizations of the \(P\) = ? \(NP\) question, SIAM J. comput., 4, 431-442, (1975) · Zbl 0323.68033
[5] Bauer, M.; Brand, D.; Fischer, M.; Meyer, A.; Paterson, M., A note on disjunctive form tautologies, SIGACT news, 5, 17-20, (April 1973)
[6] Cook, S.A., The complexity of theorem proving procedures, Proc. third annual ACM symposium on theory of computing, 151-158, (1971)
[7] Cook, S.A.; Reckhow, R.A., Time bounded random access machines, J. comput. system sci., 7, 354-375, (1973) · Zbl 0284.68038
[8] Even, S.; Tarjan, R.E., A combinatorial problem which is complete in polynomial space, Proc. seventh annual ACM symposium on theory of computing, 66-71, (1975)
[9] Fagin, R.; Karp, R., Generalized first-order spectra and polynomial-time recognizable sets, Complexity of computation, SIAM-AMS proc., 7, 43-73, (1974)
[10] Harrison, M.A., Introduction to switching and automata theory, (1965), McGraw-Hill New York · Zbl 0196.51702
[11] Hopcroft, J.E.; Ullman, J.D., Formal languages and their relation to automata, (1969), Addison-Wesley Reading, Mass · Zbl 0196.01701
[12] Jones, N.D., Space-bounded reducibility among combinatorial problems, J. comput. system sci., 11, 68-85, (1975) · Zbl 0317.02039
[13] Karp, R.M., Reducibility among combinatorial problems, (), 85-104 · Zbl 0366.68041
[14] Knuth, D.E., Postcript about NP-hard problems, SIGACT news, 6, 15-16, (April 1974)
[15] Ladner, R.E., The computational complexity of validity in T, S4, and S5, (1974), University of Washington Seattle, Wash, manuscript
[16] Lind, J.C., Computing in logarithmic space, ()
[17] Meyer, A.R.; Stockmeyer, L.J., The equivalence problem for regular expressions with squaring requires exponential space, Proc. thirteenth annual IEEE symposium on switching and automata theory, 125-129, (1972)
[18] Rogers, H., Theory of recursive functions and effective computability, (1967), McGraw-Hill New York · Zbl 0183.01401
[19] Savitch, W.J., Relationships between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, 177-192, (1970) · Zbl 0188.33502
[20] Shoenfield, J.R., Mathematical logic, (1967), Addison-Wesley Reading, Mass · Zbl 0155.01102
[21] Seiferas, J.I., Nondeterministic time and space complexity classes, () · Zbl 0274.04004
[22] Seiferas, J.I.; Fischer, M.J.; Meyer, A.R., Refinements of the nondeterministic time and space hierarchies, Proc. fourteenth annual IEEE symposium on switching and automata theory, 130-137, (1973)
[23] Stearns, R.E.; Hartmanis, J.; Lewis, P.M., Hierarchies of memory limited computations, Sixth IEEE symposium on switching circuit theory and logical design, 179-190, (1965)
[24] Stockmeyer, L.J., The complexity of decision problems in automata theory and logic, () · Zbl 0444.94037
[25] Stockmeyer, L.J.; Meyer, A.R., Word problems requiring exponential time: preliminary report, Proc. fifth annual ACM symposium on theory of computing, 1-9, (1973) · Zbl 0359.68050
[26] English Transl.: Consultants Bureau, New York, 1970, 115\2-125.
[27] Wrathall, C., Complete sets and the polynomial hierarchy, Theoret. comp. sci., 3, (1976)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.