Class Description

coNEXP: Complement of NEXP

Contained in NEXP/poly (folklore result reported in [Fortnow's weblog]).

Linked From

Check: Checkable Languages

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,

  1. If P(y)=f(y) for all inputs y, then CP(x) (C with oracle access to P) accepts with probability at least 2/3.
  2. If P(x) is not equal to f(x) then CP(x) accepts with probability at most 1/3.

Introduced in [BK89], where it was also shown that Check equals frIPcofrIP.

Check is contained in NEXPcoNEXP [FRS88].

[BG94] show that if NEE is not contained in BPEE then NP is not contained in Check.

More about...


MAE: Exponential-Time MA With Linear Exponent

Same as MA, except now Arthur is E instead of polynomial-time.

If MAE = NEE then MA = NEXPcoNEXP [IKW01].

More about...


NE/poly: Nonuniform NE

Contains coNE, just as NEXP/poly contains coNEXP.

More about...


NEE: Nondeterministic EE

Nondeterministic double-exponential time with linear exponent (i.e. NTIME(22O(n))).

If MAE = NEE then MA = NEXPcoNEXP [IKW01].

Contained in NEEXP.

More about...


NEXP/poly: Nonuniform NEXP

Contains coNEXP (folklore result reported in Fortnow's weblog).

More about...


QRG: Quantum Refereed Games

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

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.

More about...