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

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