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 (21)

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

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