New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.

DOI10.1006/jcss.2002.1835zbMath1059.68043OpenAlexW1988254244MaRDI QIDQ1872705

Johannes Köbler, V. Arvind

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

zbMATH Keywords

lownessprobabilistic classinteractive proof systemfunction classprogram checker.self-reducible set

Mathematics Subject Classification ID

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

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