Computational Complexity and the Existence of Complexity Gaps
- 1 January 1972
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 19 (1), 158-174
- https://doi.org/10.1145/321679.321691
Abstract
No abstract availableThis publication has 13 references indexed in Scilit:
- The operator gapPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1969
- Toward a theory of enumerationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1968
- Computational Complexity of One-Tape Turing Machine ComputationsJournal of the ACM, 1968
- On the size of machinesInformation and Control, 1967
- A Machine-Independent Theory of the Complexity of Recursive FunctionsJournal of the ACM, 1967
- Two-Tape Simulation of Multitape Turing MachinesJournal of the ACM, 1966
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965
- Hierarchies of memory limited computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965
- Real-Time Computation and Recursive Functions Not Real-Time ComputableIEEE Transactions on Electronic Computers, 1962
- Gödel numberings of partial recursive functionsThe Journal of Symbolic Logic, 1958