Same as RG, except that now the verifier can exchange only two messages with each prover. Messages are exchanged in parallel, so the verifier cannot process the answer from one prover before preparing the question for the other. See also RG(k).
RG(2) is contained in PSPACE, and they are equal, unrelativized [FK97b].
Same as QRG, except that now the verifier can exchange only two messages with each prover. Messages are exchanged in parallel, so the verifier cannot process the answer from one prover before preparing the question for the other. QRG(2) is the quantum version of RG(2). See also QRG(k).
QRG(2) trivially contains RG(2) (and hence PSPACE).
QRG(2) is trivially contained in SQG (and hence PSPACE). Hence QRG(2) = RG(2) = PSPACE and finding optimal strategies for two-turn zero-sum quantum games is no harder than finding optimal strategies for two-turn zero-sum classical games.
Same as RG, except that now the verifier exchanges exactly k messages with each prover where k is a polynomial-bounded function of the input length. Messages are exchanged in parallel. By definition, RG(poly) = RG. See also RG(1) and RG(2).
Other than trivial bounds, very little is known of RG(k) for intermediate values of k. For example, does RG(k) = PSPACE for each constant ?
The class of problems for which there exists a BPP machine M such that, on input x:
In other words, it's the same as RG(k) for , the class of problems that admit interactive proofs with competing provers in which there's no communication from the verifier back to the provers.
RG(1) trivially contains S2P. Indeed, RG(1) can be viewed as a randomized version of S2P.
RG(1) is trivially contained in RG(2) (and hence PSPACE).
Same as QRG(2), except that now the verifier can process the yes-prover's answer before preparing the no-prover's question.
Defined in [GW05], where it was also shown that SQG contains QIP.
SQG is contained in EXP [Gut05].
SQG is trivially contained in QRG(4) (and hence EXP).
SQG trivially contains QRG(2) (and hence PSPACE).
SQG is contained in PSPACE [GW10]. Hence SQG = QRG(2) = RG(2) = PSPACE and the addition of quantum information, combined with the ability of the verifier to process the one prover's answer before preparing the other prover's question, has no effect on the complexity of two-turn (one-round) zero-sum games.
