AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
From MaRDI portal
Publication:1029043
DOI10.1016/j.ipl.2003.09.011zbMath1178.68280OpenAlexW2000249261MaRDI QIDQ1029043
Publication date: 9 July 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2003.09.011
Related Items (2)
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Competing provers yield improved Karp-Lipton collapse results
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- Strong nondeterministic polynomial-time reducibilities
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Strong and robustly strong polynomial-time reducibilities to sparse sets
- A taxonomy of complexity classes of functions
- An oracle builder's toolkit
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- Proof verification and the hardness of approximation problems
- Circuit-size lower bounds and non-reducibility to sparse sets
- On relativized exponential and probabilistic complexity classes
- New Collapse Consequences of NP Having Small Circuits
- Algebraic methods for interactive proof systems
- IP = PSPACE
This page was built for publication: AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
