Computational Complexity and the Existence of Complexity Gaps

Cited in

(28)

A survey of information-based complexity
On the power of recursive optimizers
Complexity of algorithms and computations
The non-renamability of honesty classes
Techniques for separating space complexity classes
Relating refined space complexity classes
Some applications of the McCreight-Meyer algorithm in abstract complexity theory
Relations between diagonalization, proof systems, and complexity gaps
Reductions in circuit complexity: An isomorphism theorem and a gap theorem
Decision algorithms for multiplayer noncooperative games of incomplete information
Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees
For completeness, sublogarithmic space is no space.
Characterization of realizable space complexities
The enumerability and invariance of complexity classes
Abstract computational complexity and cycling computations
Reverse complexity
Quantitative aspects of speed-up and gap phenomena
A complexity measure for data flow models
Recent developments in information-based complexity
Honest bounds for complexity classes of recursive functions
Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
Relativization of the Theory of Computational Complexity
On generalized computational complexity
Effective category and measure in abstract complexity theory
Lower bounds for multiplayer noncooperative games of incomplete information
Effective category and measure in abstract complexity theory
Parametrization over inductive relations of a bounded number of variables
Learning recursive functions: A survey

This page was built for publication: Computational Complexity and the Existence of Complexity Gaps

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