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

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

V. Arvind, Johannes Köbler

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

lowness; probabilistic class; interactive proof system; function class; program checker.; self-reducible set

Mathematics Subject Classification ID

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

Related Items

Average-case intractability vs. worst-case intractability, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\), Complexity results in graph reconstruction, 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