Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems

DOI10.2307/2039484zbMath0328.68044OpenAlexW4234441517MaRDI QIDQ4094391

No author found.

Publication date: 1973

Full work available at URL: https://doi.org/10.2307/2039484

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (9)

On recursive bounds for the exceptional values in speed-up ⋮ Reverse complexity ⋮ Characterization of realizable space complexities ⋮ On the power of recursive optimizers ⋮ Learning recursive functions: A survey ⋮ Effective category and measure in abstract complexity theory ⋮ Effective category and measure in abstract complexity theory ⋮ Techniques for separating space complexity classes ⋮ Relating refined space complexity classes

Cites Work

• Honest bounds for complexity classes of recursive functions
• Ordinal Hierarchies and Naming Complexity Classes
• Classes of computable functions defined by bounds on computation
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Speed-Ups by changing the order in which sets are enumerated
• On Effective Procedures for Speeding Up Algorithms
• An Overview of the Theory of Computational Complexity
• The Operator Gap
• On Effectively Computable Operators
• Computational speed-up by effective operators
• On size vs. efficiency for programs admitting speed-ups
• Computational Complexity and the Existence of Complexity Gaps

This page was built for publication: Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems