Complete problems for deterministic polynomial time. (English) Zbl 0352.68068


68Q25 Analysis of algorithms and problem complexity
68W99 Algorithms in computer science
68Q45 Formal languages and automata
Full Text: DOI


[1] Chang, C.; Lee, R., Symbolic logic and mechanical theorem-proving, (1973), Academic Press New York · Zbl 0263.68046
[2] Cook, S.A., Path systems and language recognition, Proc. second ACM symp. on theory of computing, 70-72, (1970)
[3] Cook, S.A., The complexity of theorem-proving procedures, Proc. third ACM symp. on theory of computing, 151-158, (1971)
[4] Cook, S.A., An observation on time-storage trade-off, J. comput. system sci., 9, 308-316, (1974) · Zbl 0306.68026
[5] Even, S.; Tarjan, R., A combinatorial problem which is complete in polynomial space, Proc. seventh ACM symp. on theory of computing, 66-71, (1975)
[6] Henschen, L.; Wos, L., Unit refutations and Horn sets, J. ACM, 21, 4, 590-605, (1974) · Zbl 0296.68093
[7] Hopcroft, J.; Ullman, J., Formal languages and their relation to automata, (1969), Addison-Wesley Reading, Mass · Zbl 0196.01701
[8] Jones, N.D., Space-bounded reducibility among combinatorial problems, J. comput. system sci., 11, 1, 68-85, (1975) · Zbl 0317.02039
[9] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[10] Lind, J.; Meyer, A.R., A characterization of log-space computable functions, SIGACT news, 5, 3, 26-28, (1973)
[11] Stockmeyer, L.J.; Meyer, A.R., Word problems requiring exponential time: preliminary report, Proc. fifth ACM symp. on theory of computing, 1-9, (1973) · Zbl 0359.68050
[12] Younger, D.H., Recognition and parsing of context-free languages in time n3, Inform. and control, 10, 2, 189-208, (1967) · Zbl 0149.24803
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.