The Operator Gap

DOI10.1145/321679.321692MaRDI QIDQ5637883zbMATH OpenOpenAlexFDO

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
• Hierarchy of complexity of computation of partial functions with values 0 and 1
• Speed-Ups by changing the order in which sets are enumerated
• 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
• Learning recursive functions: A survey
• The enumerability and invariance of complexity classes
• 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)