Journal of the ACM Bibliography
L. H. Landweber and E. L. Robertson. Recursive
properties of abstract complexity classes. Journal of the
ACM, 19(2):296-308, April 1972.
[BibTeX entry]
Additional Key Words and Phrases:
abstract complexity measure, computational complexity, complexity class,
recursion theory, enumeration, presentation
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.
- Victor L. Bennison and Robert I. Soare. Some lowness properties
and computational complexity sequences. Theoretical Computer
Science, 6(3):233-254, June 1978.
- P. van Emde Boas. Some applications of the
McCreight-Meyer algorithm in abstract complexity theory.
Theoretical Computer Science, 7(1):79-98, August 1978.
- John Gill and Manuel Blum. On almost everywhere complex
recursive functions. Journal of the ACM, 21(3):425-435,
July 1974.
- Kenneth W. Regan. Index sets and
presentations of complexity classes. Theoretical Computer
Science, 161(1-2):263-287, 15 July 1996.
Selected references
- Manuel Blum. A
machine-independent theory of the complexity of recursive functions.
Journal of the ACM, 14(2):322-336, April 1967.
- A. Borodin. Complexity classes of
recursive functions and the existence of complexity gaps. In
Conference Record of ACM Symposium on Theory of Computing,
pages 67-78, Marina del Rey, California, 5-7 May 1969.
- 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.
- Edward L. Robertson. Complexity classes of
partial recursive functions (preliminary version). In
Conference Record of Third Annual ACM Symposium on Theory of
Computing, pages 258-266, Shaker Heights, Ohio, 3-5 1971 1971.
- Paul R. Young. Toward a
theory of enumerations. Journal of the ACM,
16(2):328-348, April 1969.
Shortcuts: