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, (Proc. 1964 Congress for Logic, Math., and Phil. of Sci. (1964), North-Holland: North-Holland Amsterdam), 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) · Zbl 0253.68020
[6] Cook, S., A hierarchy for nondeterministic time complexity, Proc. Fourth ACM Symposium on Theory of Computing, 187-192 (1972) · Zbl 0361.68074
[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, (Miller, R.; Thatcher, J., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York)
[11] Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: 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) · Zbl 0229.02033
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.