zbMATH — the first resource for mathematics

A hierarchy for nondeterministic time complexity. (English) Zbl 0278.68042

68Q25 Analysis of algorithms and problem complexity
03D10 Turing machines and related notions
Full Text: DOI
[1] Cook, S.A., The complexity of theorem-proving procedures, (), 151-158 · Zbl 0363.68125
[2] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[3] Hennie, F.C.; Stearns, R.E., Two-tape simulation of multi-tape Turing machines, J. assoc. for computing machinery, 13, 533-546, (1966) · Zbl 0148.24801
[4] Ibarra, Oscar, A note concerning nondeterministic tape complexities, J. assoc. for computing machinery, 19, 608-612, (1972) · Zbl 0245.94044
[5] Savitch, Walter, Relationships between nondeterministic and deterministic tape complexities, J. computer and system sciences, 4, 177-192, (1970) · Zbl 0188.33502
[6] \scS. Ruby and P. C. Fischer, Translational methods in computational complexity, 1965 IEEE Conference Record on Switching Circuit Theory, and Logical Design, Sixth Annual Symposium, pp. 173-178. · Zbl 0257.68037
[7] \scA. R. Meyer, A. L. Rosenberg, and P. C. Fischer, Multi-tape simulation of multi-head Turing machines, IEEE Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, 117-127.
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.