The enumerability and invariance of complexity classes

DOI10.1016/S0022-0000(71)80037-5MaRDI QIDQ2545514zbMATH OpenFDO

Authors Forbes D. Lewis

Publication date 1971

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0022-0000(71)80037-5

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites work

• A Machine-Independent Theory of the Complexity of Recursive Functions
• Classes of computable functions defined by bounds on computation
• Computational Complexity and the Existence of Complexity Gaps
• Gödel numberings of partial recursive functions
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• On the Computational Complexity of Algorithms
• Recursive Properties of Abstract Complexity Classes
• Some Theorems on Classes of Recursively Enumerable Sets
• The Operator Gap
• Toward a Theory of Enumerations

Cited in

(6)

• Complexity of algorithms and computations
• Two types of properties for complexity measures
• Toward a mathematical theory of graph-generative systems and its applications
• ``Natural properties of flowchart step-counting measures
• Abstract computational complexity and cycling computations
• scientific article; zbMATH DE number 3644481 (Why is no real title available?)

This page was built for publication: The enumerability and invariance of complexity classes

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