Recursive Properties of Abstract Complexity Classes

DOI10.1145/321694.321702MaRDI QIDQ5677072zbMATH OpenOpenAlexFDO

Authors Lawrence H. Landweber, Edward L. Robertson

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)

Cited in

(21)

• 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
• Complexity classes of partial recursive functions
• 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
• Index sets and presentations of complexity classes
• The enumerability and invariance of complexity classes
• Subrecursive programming languages. II. On program size
• Abstract computational complexity and cycling computations
• Reverse complexity
• On the amount of nonconstructivity in learning recursive functions
• Recursively enumerable complexity sequences and measure independence
• Honest bounds for complexity classes of recursive functions
• Relativization of the Theory of Computational Complexity
• Computational complexity, speedable and levelable sets
• Implicit measurements of dynamic complexity properties and splittings of speedable sets
• Learning recursive functions: A survey

This page was built for publication: Recursive Properties of Abstract Complexity Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5677072)