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 ?
Same as QRG, 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. QRG(k) is the quantum version of RG(k). By definition, QRG(poly) = QRG. See also QRG(1) and QRG(2).
QRG(k) trivially contains RG(k) for each k (and hence PSPACE when ). QRG(4) trivially contains SQG.
QRG(k) is trivially contained in QRG for each k (and hence EXP).
Other than these trivial bounds, very little is known of QRG(k) for intermediate values of k. For example, does QRG(k) = RG(k) for each k?
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].
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).
