ON HIGHER ARTHUR-MERLIN CLASSES

DOI10.1142/S0129054104002273MaRDI QIDQ5696962zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Denis Xavier Charles, Aduri Pavan, Samik Sengupta

Publication date 19 October 2005

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

Full work available at URL https://doi.org/10.1142/s0129054104002273

zbMATH Keywords

Arthur-Merlin gamespolynomial-time hierarchyprobabilistic operators

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2089956
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• scientific article; zbMATH DE number 4050983
• Relativized Arthur-Merlin versus Merlin-Arthur games
• Probabilistic quantifiers and games

Cites work

• A complexity theory for feasible closure properties
• A decisive characterization of BPP
• Algebraic methods for interactive proof systems
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Complexity classes of optimization functions
• Does co-NP have short interactive proofs ?
• Graph isomorphism is in the low hierarchy
• scientific article; zbMATH DE number 1379310 (Why is no real title available?)
• IP = PSPACE
• Non-deterministic exponential time has two-prover interactive protocols
• On pseudorandomness and resource-bounded measure
• On the limits of nonapproximability of lattice problems
• PP is as Hard as the Polynomial-Time Hierarchy
• Probabilistic complexity classes and lowness
• Relativized circuit complexity
• Symmetric alternation captures BPP
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• The Formula Isomorphism Problem
• The operators min and max on the polynomial hierarchy

Cited in

(4)

• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Relativized Arthur-Merlin versus Merlin-Arthur games
• scientific article; zbMATH DE number 4057011 (Why is no real title available?)
• scientific article; zbMATH DE number 2089956 (Why is no real title available?)

This page was built for publication: ON HIGHER ARTHUR-MERLIN CLASSES

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