Class Description

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 ${\displaystyle k=1}$, 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 S₂P. Indeed, RG(1) can be viewed as a randomized version of S₂P.

RG(1) is trivially contained in RG(2) (and hence PSPACE).

Linked From

QRG(1): One-turn Quantum Refereed Games

The class of problems for which there exists a BQP machine M such that:

• If the answer is "yes," then there exists a quantum state ρ such that for all quantum states σ, M(ρ,σ) accepts with probability at least 2/3.
• If the answer is "no," then there exists a σ such that for all ρ, M(ρ,σ) rejects with probability at least 2/3.

In other words, it's the same as QRG(k) for ${\displaystyle k=1}$, the class of problems that admit quantum interactive proofs with competing provers in which there's no communication from the verifier back to the provers. QRG(1) is the quantum version of RG(1).

Defined in [JW09], where it was shown that QRG(1) is contained in PSPACE .

QRG(1) trivially contains QMA (and indeed P^QRG(1)).

QRG(1) is trivially contained in QRG(2) (and hence PSPACE).

More about...

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 ${\displaystyle k\geq 2}$?

More about...