Structural complexity theory: Recent surprises

DOI10.1007/3-540-52846-6_73zbMath1502.68129OpenAlexW1812177553MaRDI QIDQ5056087

Desh Ranjan, Richard Chang, Pankaj Rohatgi, Juris Hartmanis

Publication date: 9 December 2022

Published in: SWAT 90 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-52846-6_73

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The random oracle hypothesis is false, On random oracle separations, The generic oracle hypothesis is false, The robustness of LWPP and WPP, with an application to graph reconstruction, A note on enumerative counting

Cites Work

• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Are there interactive protocols for co-NP languages?
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Computational Complexity of Probabilistic Turing Machines
• The isomorphism conjecture fails relative to a random oracle