Class Description

RG(k): k-turn Refereed 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 ?

Linked From

QRG(k): k-turn Quantum Refereed Games

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?

More about...


RG(2): Two-turn (one-round) Refereed Games

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

More about...


RG(1): One-turn Refereed Games

The class of problems for which there exists a BPP machine M such that, on input x:

  1. If the answer is 'yes,' then there exists a distribution Y such that for all distributions Z, M(x,Y,Z) accepts with probability at least 2/3.
  2. If the answer is 'no,' then there exists a distribution Z such that for all distributions Y, M(x,Y,Z) rejects with probability at least 2/3.

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

More about...