Class Description

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.

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


Coh: Coherent Languages

The class of problems L that are efficiently autoreducible, in the sense that given an input x and access to an oracle for L, a BPP machine can compute L(x) by querying L only on points that differ from x.

Defined in [Yao90b].

[BG94] show that, assuming NEE is not contained in BPEE, Coh ∩ NP is not contained in any of compNP, Check, or frIP.

More about...


compIP: Competitive IP Proof System

Same as compNP but for interactive (IP) proofs instead of NP proofs.

More formally, compIP is the class of decision problems L in IP = PSPACE such that, if the answer is "yes," then that can be proven by an interactive protocol between a BPP verifier and a prover, a BPP machine with access only to an oracle for L.

Assuming NEE is not contained in BPEE, NP (and indeed NPCoh) is not contained in compIP [BG94].

More about...


compNP: Competitive NP Proof System

The class of decision problems L in NP such that, if the answer is "yes," then a proof can be constructed in polynomial time given access only to an oracle for L.

Contains NPC.

[BG94] show that compNP is contained in frIP, and that assuming NEE is not contained in BPEE, compNP does not equal NP.

More about...


EE: Double-Exponential Time With Linear Exponent

Equals DTIME(22O(n)) (though some authors alternatively define it as being equal to DTIME(2O(2n))).

EE = BPE if and only if EXP = BPP [IKW01].

Contained in EEXP and NEE.

More about...


FNP: Function NP

The class of function problems of the following form:

FNP generalizes NP, which is defined in terms of decision problems only.

Actually the word "function" is misleading, since there could be many valid outputs y. That's unavoidable, since given a predicate F there's no "syntactic" criterion ensuring that y is unique.

FP = FNP if and only if P = NP.

Contains TFNP.

A basic question about FNP problems is whether they're self-reducible; that is, whether they reduce to the corresponding NP decision problems. Although this is true for all NPC problems, [BG94] shows that if EE does not equal NEE, then there is a problem in NP such that no corresponding FNP problem can be reduced to it. [BG94] cites Impagliazzo and Sudan as giving the same conclusion under the assumption that NE does not equal coNE.

More about...


frIP: Function-Restricted IP Proof Systems

The class of problems L that have a decider in the following sense. There exists a BPP machine D such that for all inputs x,

  1. If the answer is "yes" then DL(x) (D with oracle for L) accepts with probability at least 2/3.
  2. If the answer is "no" then DA(x) accepts with probability at most 1/3 for all oracles A.

Contains compIP [BG94] and Check [BK89].

Contained in MIP = NEXP [FRS88].

Assuming NEE is not contained in BPEE, NP (and indeed NPCoh) is not contained in frIP [BG94].

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