Computational Complexity and the Existence of Complexity Gaps

DOI10.1145/321679.321691zbMath0261.68024OpenAlexW2043382625WikidataQ59794643 ScholiaQ59794643MaRDI QIDQ5677071

Allan Borodin

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.321691

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (28)

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

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