Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
From MaRDI portal
Publication:4094391
DOI10.2307/2039484zbMath0328.68044OpenAlexW4234441517MaRDI QIDQ4094391
No author found.
Publication date: 1973
Full work available at URL: https://doi.org/10.2307/2039484
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
