New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
From MaRDI portal
Publication:1872705
DOI10.1006/jcss.2002.1835zbMath1059.68043OpenAlexW1988254244MaRDI QIDQ1872705
Publication date: 14 May 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.2002.1835
Related Items
\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) ⋮ Complexity results in graph reconstruction ⋮ Average-case intractability vs. worst-case intractability ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Relations between average-case and worst-case complexity ⋮ AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- A low and a high hierarchy within NP
- Relativized Arthur-Merlin versus Merlin-Arthur games
- Circuit size relative to pseudorandom oracles
- Probabilistic complexity classes and lowness
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- A taxonomy of complexity classes of functions
- Hardness vs randomness
- Oracles and queries that are sufficient for exact learning
- Self-reducibility
- Quantitative Relativizations of Complexity Classes
- Bounded Round Interactive Proofs in Finite Groups
- New Collapse Consequences of NP Having Small Circuits
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Designing programs that check their work
