Uniform generation of NP-witnesses using an NP-oracle

DOI10.1006/inco.2000.2885zbMath1006.68050OpenAlexW2094975553MaRDI QIDQ1854397

Mihir Bellare, Erez Petrank, Oded Goldreich

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/1fc04f4dcb80557c17f003ae4297f7d44f4cd224

Mathematics Subject Classification ID

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

Related Items

On the complexity of interactive proofs with bounded communication, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Circuit lower bounds from learning-theoretic approaches, \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\), Approximate counting in SMT and value estimation for probabilistic programs, (Nondeterministic) hardness vs. non-malleability, On the impossibility of key agreements from quantum random oracles, How to get more mileage from randomness extractors, On Pseudodeterministic Approximation Algorithms., On the (im-)possibility of extending coin toss, Lower bounds for non-black-box zero knowledge, Advanced SMT techniques for weighted model integration

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of interactive proofs with bounded communication
• Non-deterministic exponential time has two-prover interactive protocols
• Statistical zero-knowledge languages can be recognized in two rounds
• Random generation of combinatorial structures from a uniform distribution
• NP is as easy as detecting unique solutions
• The probabilistic method yields deterministic parallel algorithms
• Computational complexity and knowledge complexity (extended abstract)
• The Knowledge Complexity of Interactive Proof Systems
• Simulating (log ^c n )-wise independence in NC