Polynomial-Space Approximation of No-Signaling Provers

摘要: In two-prover one-round interactive proof systems, nosignaling provers are those who allowed to use arbitrary strategies, not limited local operations, as long their strategies cannot be used for communication between them. The study of multi-prover systems with no-signaling has been motivated by the sharing quantum states. relation them is that include all realizable entangled states, and more. It was known PSPACE ⊆ MIPns(2, 1) EXP, where class languages having a system provers. This paper shows = PSPACE. This proved constructing fast parallel algorithm which approximates within an additive error maximum winning probability players in given cooperative two-player game. uses mixed packing covering problem Young (FOCS 2001).