The Operator Gap

DOI10.1145/321679.321692zbMATH Open0229.68016OpenAlexW2081635977MaRDI QIDQ5637883FDOQ5637883

Authors: Robert Constable 

Publication date: 1972

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

Full work available at URL: https://doi.org/10.1145/321679.321692

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (15)

• Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
• Relating refined space complexity classes
• Techniques for separating space complexity classes
• Characterization of realizable space complexities
• Speed-Ups by changing the order in which sets are enumerated
• Hierarchy of complexity of computation of partial functions with values 0 and 1
• Relativization of the Theory of Computational Complexity
• Honest bounds for complexity classes of recursive functions
• On generalized computational complexity
• The operator gap theorem in α-recursion theory
• Effective category and measure in abstract complexity theory
• The enumerability and invariance of complexity classes
• Learning recursive functions: A survey
• The non-renamability of honesty classes
• Effective category and measure in abstract complexity theory

This page was built for publication: The Operator Gap

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