Computer Science – Computational Complexity
Scientific paper
2009-08-17
Computer Science
Computational Complexity
13 pages. v2: Introduction expanded, references added, some open problems stated, and typos corrected
Scientific paper
In two-prover one-round interactive proof systems, no-signaling provers are those who are allowed to use arbitrary strategies, not limited to local operations, as long as their strategies cannot be used for communication between them. Study of multi-prover interactive proof systems with no-signaling provers is motivated by study of those with provers sharing quantum states. The relation between them is that no-signaling strategies include all the strategies realizable by provers sharing arbitrary entangled quantum states, and more. This paper shows that two-prover one-round interactive proof systems with no-signaling provers only accept languages in PSPACE. Combined with the protocol for PSPACE by Ito, Kobayashi and Matsumoto (CCC 2009), this implies MIPns(2,1)=PSPACE, where MIPns(2,1) is the class of languages having a two-prover one-round interactive proof system with no-signaling provers. This is proved by constructing a fast parallel algorithm which approximates within an additive error the maximum value of a two-player one-round game achievable by cooperative no-signaling players. The algorithm uses the fast parallel algorithm for the mixed packing and covering problem by Young (FOCS 2001).
No associations
LandOfFree
Polynomial-Space Approximation of No-Signaling Provers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Polynomial-Space Approximation of No-Signaling Provers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial-Space Approximation of No-Signaling Provers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-19692