If NP has polynomial-size circuits, then MA=AM

DOI10.1016/0304-3975(95)91133-BzbMath0874.68185MaRDI QIDQ674343

Johannes Köbler, Rainer Schuler, V. Arvind, Uwe Schoening

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

NPpolynomial-size circuits

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55)

Related Items

The Untold Story of $$\mathsf {SBP}$$ ⋮ \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) ⋮ Arthur and Merlin as oracles ⋮ Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy ⋮ NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ A note on the circuit complexity of PP

Cites Work

• BPP and the polynomial hierarchy
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• On relativized exponential and probabilistic complexity classes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: If NP has polynomial-size circuits, then MA=AM