The enumerability and invariance of complexity classes. (English) Zbl 0215.04701


03D15 Complexity of computation (including implicit computational complexity)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI


[1] Blum, M., A machine independent theory of the complexity of recursive functions, Jacm, 14, 322-336, (1967) · Zbl 0155.01503
[2] Borodin, A., Complexity classes of recursive functions and the existence of complexity gaps, () · Zbl 0261.68024
[3] Borodin, A.; Constable, R.; Hopcroft, J., Dense and non-dense families of complexity classes, ()
[4] Constable, R., On the size of programs in subrecursive formalisms, (), 1-9
[5] Constable, R., The operator gap, () · Zbl 0229.68016
[6] Constable, R.; Borodin, A., On the efficiency of programs in subrecursive formalisms, ()
[7] Dekker, J.C.E.; Myhill, J., Some theorems on classes of recursively enumerable sets, Trans. amer. math. soc., 89, 25-59, (1958) · Zbl 0083.00302
[8] Hartmanis, J.; Stearns, R., On the computational complexity of algorithms, Trans. amer. math. soc., 117, 285-306, (1965) · Zbl 0131.15404
[9] Lewis, F.D., The classification of unsolvable problems in automata theory, ()
[10] Lewis, F.D., Unsolvability considerations in computational complexity, ()
[11] {\scF. D. Lewis}, Classes of Recursive Functions and their Index Sets, submitted for publication.
[12] McCreight, E.; Meyer, A., Classes of computable functions defined by bounds on computation, (), 79-88 · Zbl 1283.03074
[13] Meyer, A.; Fischer, P., On computational speedup, (), 351-355
[14] Myhill, J., Linear bounded automata, Univ. of penna. rpt. no. 60-22, (1960)
[15] Landweber, L.H.; Robertson, E.L., On recursive properties of complexity classes, () · Zbl 0261.68025
[16] Rogers, H.G., Gödel numberings of partial recursive functions, Jsl, 23, 331-341, (1958) · Zbl 0088.01602
[17] Rogers, H.G., ()
[18] Stearns, R.; Hartmanis, J.; Lewis, P., II. hierarchies of memory limited computations, (), 179-190 · Zbl 0229.02033
[19] Young, P., Toward a theory of enumerations, Jacm, 16, 328-347, (1969) · Zbl 0191.30801
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.