The enumerability and invariance of complexity classes

DOI10.1016/S0022-0000(71)80037-5zbMath0215.04701MaRDI QIDQ2545514

Forbes D. Lewis

Publication date: 1971

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

Mathematics Subject Classification ID

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

Related Items (6)

Unnamed Item ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Some Theorems on Classes of Recursively Enumerable Sets
• Gödel numberings of partial recursive functions
• On the Computational Complexity of Algorithms
• Classes of computable functions defined by bounds on computation
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Toward a Theory of Enumerations
• The Operator Gap
• Computational Complexity and the Existence of Complexity Gaps
• Recursive Properties of Abstract Complexity Classes

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