The two queries assumption and Arthur-Merlin classes

DOI10.1007/978-3-662-44465-8_51MaRDI QIDQ2922647zbMATH OpenOpenAlexFDO

Authors Vyas Ram Selvam

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44465-8_51

zbMATH Keywords

Arthur-Merlin classescomputational complexitySAT oracletwo-queries assumption

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin
• scientific article; zbMATH DE number 1335876
• The 1-Versus-2 Queries Problem Revisited
• Arthur and Merlin as oracles
• If NP has polynomial-size circuits, then MA=AM

Cited in

(4)

• Two queries
• Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin
• Oblivious Symmetric Alternation
• If NP has polynomial-size circuits, then MA=AM

This page was built for publication: The two queries assumption and Arthur-Merlin classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922647)