Relativized Arthur-Merlin versus Merlin-Arthur games

DOI10.1016/0890-5401(89)90022-9zbMath0667.03031OpenAlexW2013587815MaRDI QIDQ1117218

Miklos Santha

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90022-9

zbMATH Keywords

oraclecomplexity classesArthur-Merlin games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., Zero-information protocols and unambiguity in Arthur-Merlin communication, Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\), Non-deterministic exponential time has two-prover interactive protocols, A uniform approach to define complexity classes, On pseudorandomness and resource-bounded measure, Error-bounded probabilistic computations between MA and AM

Cites Work

• Unnamed Item
• Does co-NP have short interactive proofs ?
• A second step toward the polynomial hierarchy
• The knowledge complexity of interactive proof-systems