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.