Journal of the ACM Bibliography

Additional Key Words and Phrases: computational complexity, measures of complexity, recursive functions, tape complexity, step counting functions, axiomatic complexity theory

Selected papers that cite this one

• Leonard Bass and Paul Young. Ordinal hierarchies and naming complexity classes. Journal of the ACM, 20(4):668-686, October 1973.

• A. Borodin. Corrigendum: ``Computational complexity and the existence of complexity gaps''. Journal of the ACM, 19(3):576, July 1972.

• John Gill and Manuel Blum. On almost everywhere complex recursive functions. Journal of the ACM, 21(3):425-435, July 1974.

• Juris Hartmanis. Relations between diagonalization, proof systems, and complexity gaps. Theoretical Computer Science, 8(2):239-253, April 1979.

• Joel I. Seiferas and Albert R. Meyer. Characterizations of realizable space complexities. Annals of Pure and Applied Logic, 73(2):171-190, 1 June 1995.

• H. Wo\'zniakowski. A survey of information-based complexity. Journal of Complexity, 1(1):11-44, October 1985.

Selected references

• Manuel Blum. A machine-independent theory of the complexity of recursive functions. Journal of the ACM, 14(2):322-336, April 1967.

• Manuel Blum. On the size of machines. Information and Control, 11(3):257-265, September 1967.

• A. Borodin, R. L. Constable, and J. E. Hopcroft. Dense and non-dense families of complexity classes. In Conference Record of 1969 Tenth Annual Symposium on Switching and Automata Theory, pages 7-19, Waterloo, Ontario, Canada, 15-17 October 1969. IEEE.

• Robert L. Constable. The operator gap. In Conference Record of 1969 Tenth Annual Symposium on Switching and Automata Theory, pages 20-26, Waterloo, Ontario, Canada, 15-17 October 1969. IEEE.

• Patrick C. Fischer, Juris Hartmanis, and Manuel Blum. Tape reversal complexity hierarchies. In Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pages 373-382, Schenectady, New York, 15-18 October 1968. IEEE.

• J. Hartmanis. Computational complexity of one-tape Turing machine computations. Journal of the ACM, 15(2):325-339, April 1968.

• F. C. Hennie and R. E. Stearns. Two-tape simulation of multitape Turing machines. Journal of the ACM, 13(4):533-546, October 1966.

• L. H. Landweber and E. L. Robertson. Recursive properties of abstract complexity classes (preliminary version). In Conference Record of Second Annual ACM Symposium on Theory of Computing, pages 31-36, Northampton, Massachusetts, 4-6 May 1970.

• F. D. Lewis. Unsolvability considerations in computational complexity. In Conference Record of Second Annual ACM Symposium on Theory of Computing, pages 22-30, Northampton, Massachusetts, 4-6 May 1970.

• E. M. McCreight and A. R. Meyer. Classes of computable functions defined by bounds on computation: Preliminary report. In Conference Record of ACM Symposium on Theory of Computing, pages 79-88, Marina del Rey, California, 5-7 May 1969.

• Albert Meyer and Patrick C. Fischer. On computational speed-up. In Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pages 351-355, Schenectady, New York, 15-18 October 1968. IEEE.

• R. E. Stearns, J. Hartmanis, and P. M. Lewis II. Hierarchies of memory limited computations. In Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pages 179-190. IEEE, 1965.

• Paul R. Young. Toward a theory of enumerations. In Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pages 334-350, Schenectady, New York, 15-18 October 1968. IEEE.

Shortcuts: