Translational lemmas, polynomial time, and \((\log n)^j\)-space. (English) Zbl 0326.68030


68Q25 Analysis of algorithms and problem complexity
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
Full Text: DOI


[1] Book, R., On languages accepted in polynomial time, SIAM J. comput., 1, 281-287, (1972) · Zbl 0235.68027
[2] Book, R., Comparing complexity classes, J. comput. system sci., 9, 213-229, (1974) · Zbl 0331.02020
[3] Cobham, A., The intrinsic computational difficulty of functions, (), 24-30
[4] Cook, S., Characterizations of pushdown machines in terms of time-bounded computers, J. ACM, 18, 4-18, (1971) · Zbl 0222.02035
[5] Cook, S., The complexity of theorem-proving procedures, Proc. third ACM symposium on theory of computing, 151-158, (1971)
[6] Cook, S., A hierarchy for nondeterministic time complexity, Proc. fourth ACM symposium on theory of computing, 187-192, (1972)
[7] Greibach, S., The hardest context-free language, SIAM J. comput., 2, 304-310, (1973) · Zbl 0278.68073
[8] Hartmanis, J.; Stearns, R., On the computational complexity of algorithms, Trans. am. math. soc., 117, 285-306, (1965) · Zbl 0131.15404
[9] Ibarra, O., A note concerning nondeterministic tape complexities, J. ACM, 19, 608-612, (1972) · Zbl 0245.94044
[10] Karp, R., Reducibilities among combinational problems, ()
[11] Rogers, H., Theory of recursive functions and effective computability, (1967), McGraw-Hill New York · Zbl 0183.01401
[12] Ruby, S.; Fischer, P.C., Translational methods and computational complexity, Conf. record IEEE sixth annual symp. on switching circuit theory and logical design, 173-178, (1965) · Zbl 0257.68037
[13] Savitch, W., Relationships between nondeterministic and deterministic tape complexity, J. comput. system sci., 4, 177-192, (1970) · Zbl 0188.33502
[14] Stearns, R.; Hartmanis, J.; Lewis, P., Hierarchies of memory limited computations, Conf. record IEEE sixth annual symposium on switching circuit theory and logical design, 179-190, (1965)
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.