×

The polynomial-time hierarchy. (English) Zbl 0353.02024


MSC:

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
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ackermann, W., Solvable Cases of the Decision Problem (1954), North-Holland: 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: 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: 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) · Zbl 0253.68020
[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) · Zbl 0303.68035
[10] Harrison, M. A., Introduction to Switching and Automata Theory (1965), McGraw-Hill: McGraw-Hill New York · Zbl 0196.51702
[11] Hopcroft, J. E.; Ullman, J. D., Formal Languages and their Relation to Automata (1969), Addison-Wesley: 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, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 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: University of Washington Seattle, Wash, manuscript
[16] Lind, J. C., Computing in logarithmic space, (Tech. Memo. 52 (1974), M.I.T., Project MAC: M.I.T., Project MAC Cambridge, Mass)
[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: 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: Addison-Wesley Reading, Mass · Zbl 0155.01102
[21] Seiferas, J. I., Nondeterministic time and space complexity classes, (Doctoral Thesis. Doctoral Thesis, Report TR-137 (1974), M.I.T., Project MAC: M.I.T., Project MAC Cambridge, Mass) · 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) · Zbl 0229.02033
[24] Stockmeyer, L. J., The complexity of decision problems in automata theory and logic, (Doctoral Thesis. Doctoral Thesis, Report TR-133 (1974), M.I.T., Project MAC: M.I.T., Project MAC Cambridge, Mass) · 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.; 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. 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.