Recursive Properties of Abstract Complexity Classes

DOI10.1145/321694.321702zbMath0261.68025OpenAlexW2021141490MaRDI QIDQ5677072

Edward L. Robertson, Lawrence H. Landweber

Publication date: 1972

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://digital.library.wisc.edu/1793/57612

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Reverse complexity, Index sets and presentations of complexity classes, On the power of recursive optimizers, Complexity of algorithms and computations, Two types of properties for complexity measures, On the structure of sets in NP and other complexity classes, Learning recursive functions: A survey, Honest bounds for complexity classes of recursive functions, On the Amount of Nonconstructivity in Learning Recursive Functions, Complexity classes of partial recursive functions, Implicit measurements of dynamic complexity properties and splittings of speedable sets, On computational reducibility, ``Natural properties of flowchart step-counting measures, Some applications of the McCreight-Meyer algorithm in abstract complexity theory, Some lowness properties and computational complexity sequences, Computational complexity, speedable and levelable sets, Recursively enumerable complexity sequences and measure independence, The enumerability and invariance of complexity classes, Subrecursive programming languages. II. On program size, Abstract computational complexity and cycling computations, Relativization of the Theory of Computational Complexity