  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).
