Summary
An attempt is made to present a framework for the diverse complete problems that have been found. A new concept—a Hierarchy of Complete Problems is defined. Several hierarchies in various domains such as graph theory, automata theory, theorem proving and games are established.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Cook, S. A.: The complexity of theorem proving procedures. Proceedings of 3rd Annual ACM Symposium of Theory of Computing, Sheiker Heights (Ohio) 1971, p. 151–158
Cook, S. A.: An observation on time-storage trade off. Proceedings of 5th Annual ACM Symposium on Theory of Computing, Austin (Tex.) 1973, p. 29–33
Even, S., Tarjan, R. E.: A combinational problem which is complete in polynomial space. Proceedings of 7th Annual ACM Symposium on Theory of Computing, Albuquerque (New Mexico) 1975, p. 66–71
Galil, Z.: On some direct encodings of nondeterministic Turing machines operating in polynomial time into P-complete problems. SIGACT News 6, 19–24 January 1974
Gardner, M.: The fantastic combinations of John Conway's new solitaire game ‘Life’. Scientific American 223, 120–123 (1970)
Garey, M. R., Johnson, D. S., Stockmeyer, L. J.: Some simplified NP-complete problems. Proceedings of 6th ACM Symposium on Theory of Computing, Seattle (Wash.) 1974, p. 91–95
Gill, J. T.: Computational complexity of probabilistic Turing machines. Proceedings 6th Annual ACM Symposium on Theory of Computing, Seattle (Wash.) 1974, p. 91–95
Greibach, S. A.: Checking automata and one-way stack languages. J. Computer and System Sciences 3, 196–217 (1969)
Hartmanis, J., Hunt, III., H. B.: The LBA problem and its importance in the theory of computing. Cornell University, Technical Report 73–171, 1973
Hopcroft, J. E., Ullman, J. D.: Formal languages and their relation to automata. Reading (Mass.): Addison-Wesley 1969
Jones, N. D.: Reducibility among combinatorial problems in logn space. Proceedings of 7th Annual Princeton Conference on Information Sciences and Systems, 1973, p. 547–551
Jones, N. D., Laaser, W. T.: Complete problems for deterministic polynomial time. Proceedings of 6th Annual ACM Symposium on Theory of Computing, Seattle (Wash.) 1974, p. 40–46
Karp, R. M.: Reducibilities among combinatorial problems. In: Miller, R., Thatcher, J. (eds): Complexity of computer computations. New York: Plenum Press 1972, p. 85–104
Ladner, R., Lynch, N., Selman, A.: Comparison of polynomial time reducibilities. Proceedings of 6th Annual ACM Symposium on Theory of Computing, Seattle (Wash.) 1974, p. 110–121
Meyer, A. R., Stockmeyer, L. J.: Word problems requiring exponential time. Proceedings of 5th Annual ACM Symposium on Theory of Computing, Austin (Tex.) 1973, p. 1–9
Rogers, J., Jr.: Theory of recursive functions and effective computability. New York: McGraw-Hill 1967
Savitch, W. J.: Relationship between nondeterministic and deterministic tape complexities. J. Computer and System Sciences 4, 177–192 (1970)
Author information
Authors and Affiliations
Additional information
Some of the results in this paper were presented in the John Hopkins Conference on Information Sciences and Systems, April 1975.
Rights and permissions
About this article
Cite this article
Galil, Z. Hierarchies of complete problems. Acta Informatica 6, 77–88 (1976). https://doi.org/10.1007/BF00263744
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF00263744