PSPACE is provable by two provers in one round

DOI10.1016/S0022-0000(05)80026-1zbMath0802.68055OpenAlexW2032606560MaRDI QIDQ1318475

Anne Condon, Richard J. Lipton, Jin-Yi Cai

Publication date: 27 April 1994

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80026-1

zbMATH Keywords

PSPACEinteractive proof system

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Towards the parallel repetition conjecture ⋮ Fully parallelized multi-prover protocols for NEXP-time ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Quantum multi-prover interactive proof systems with limited prior entanglement. ⋮ On games of incomplete information ⋮ Parallelization of entanglement-resistant multi-prover interactive proofs ⋮ PSPACE has constant-round quantum interactive proof systems

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Non-deterministic exponential time has two-prover interactive protocols
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• On games of incomplete information
• Fully parallelized multi-prover protocols for NEXP-time
• PP is as Hard as the Polynomial-Time Hierarchy
• The Knowledge Complexity of Interactive Proof Systems
• Algebraic methods for interactive proof systems
• IP = PSPACE

This page was built for publication: PSPACE is provable by two provers in one round