The enumerability and invariance of complexity classes
- 30 June 1971
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 5 (3) , 286-303
- https://doi.org/10.1016/s0022-0000(71)80037-5
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- R. E. Stearns, J. Hartmanis, and P. M. LewisII. Hierarchies of memory limited computations. Sixth Annual Symposium on Switching Circuit Theory and Logical Design, University of Michigan, Ann Arbor, Mich., The Institute of Electrical and Electronics Engineers, Inc., New York 1965, pp. 179–190.The Journal of Symbolic Logic, 1972
- The Operator GapJournal of the ACM, 1972
- On the size of programs in subrecursive formalismsPublished by Association for Computing Machinery (ACM) ,1970
- Dense and non-dense families of complexity classesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1969
- Toward a Theory of EnumerationsJournal of the ACM, 1969
- Classes of computable functions defined by bounds on computationPublished by Association for Computing Machinery (ACM) ,1969
- A Machine-Independent Theory of the Complexity of Recursive FunctionsJournal of the ACM, 1967
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965
- Gödel numberings of partial recursive functionsThe Journal of Symbolic Logic, 1958
- Some theorems on classes of recursively enumerable setsTransactions of the American Mathematical Society, 1958