Contained in NEXP/poly (folklore result reported in [Fortnow's weblog]).
The class of problems such that a polynomial-time program P that allegedly solves them can be checked efficiently. That is, f is in Check if there exists a BPP algorithm C such that for all programs P and inputs x,
Introduced in [BK89], where it was also shown that Check equals frIP ∩ cofrIP.
Check is contained in NEXP ∩ coNEXP [FRS88].
[BG94] show that if NEE is not contained in BPEE then NP is not contained in Check.
Same as MA, except now Arthur is E instead of polynomial-time.
If MAE = NEE then MA = NEXP ∩ coNEXP [IKW01].
Contains coNE, just as NEXP/poly contains coNEXP.
Nondeterministic double-exponential time with linear exponent (i.e. NTIME(22O(n))).
If MAE = NEE then MA = NEXP ∩ coNEXP [IKW01].
Contained in NEEXP.
Contains coNEXP (folklore result reported in Fortnow's weblog).
Same as RG, except that now the verifier is a BQP machine, and can exchange polynomially many quantum messages with the competing provers.
The two provers are computationally unbounded, but must obey the laws of quantum mechanics. Also, we can assume without loss of generality that the provers share no entanglement, because adversaries gain no advantage by sharing information.
Defined in [Gut05], where it was also shown that QRG is contained in NEXP ∩ coNEXP.
QRG trivially contains RG (and hence EXP), as well as SQG.
QRG is contained in EXP [GW07]. Hence QRG = RG = EXP and finding optimal strategies for zero-sum quantum games is no harder than finding optimal strategies for zero-sum classical games.