Class Description

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.

Linked From

BPE: Bounded-Error Probabilistic E

Has the same relation to E as BPP does to P.

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

More about...


BPEE: Bounded-Error Probabilistic EE

Has the same relation to EE as BPP does to P.

More about...


EEE: Triple-Exponential Time With Linear Exponent

Equals DTIME(222O(n)).

In contrast to the case of EE, it is not known whether EEE = BPEE implies EE = BPE [IKW01].

More about...


EEXP: Double-Exponential Time

Equals DTIME(22p(n)) for p a polynomial.

Also known as 2-EXP.

Contains EE, and is contained in NEEXP.

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


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


ZPE: Zero-Error Probabilistic E

Same as ZPP, but with 2O(n)-time instead of polynomial-time.

ZPE = EE if and only if ZPP = EXP [IKW01].

More about...