ON HIGHER ARTHUR-MERLIN CLASSES

DOI10.1142/S0129054104002273zbMath1101.68594OpenAlexW2065540126MaRDI QIDQ5696962

Denis Xavier Charles, Samik Sengupta, A. Pavan, Jin-Yi Cai

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

polynomial-time hierarchyArthur-Merlin gamesprobabilistic operators

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Relativized circuit complexity
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• Graph isomorphism is in the low hierarchy
• Probabilistic complexity classes and lowness
• Symmetric alternation captures BPP
• On the limits of nonapproximability of lattice problems
• Complexity classes of optimization functions
• A complexity theory for feasible closure properties
• PP is as Hard as the Polynomial-Time Hierarchy
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• Algebraic methods for interactive proof systems
• IP = PSPACE
• The Formula Isomorphism Problem
• A decisive characterization of BPP
• THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY
• On pseudorandomness and resource-bounded measure

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