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].
Has the same relation to E as BPP does to P.
EE = BPE if and only if EXP = BPP [IKW01].
Has the same relation to EE as BPP does to P.
Equals DTIME(222O(n)).
In contrast to the case of EE, it is not known whether EEE = BPEE implies EE = BPE [IKW01].
Equals DTIME(22p(n)) for p a polynomial.
Also known as 2-EXP.
Contains EE, and is contained in NEEXP.
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.
Nondeterministic double-exponential time with linear exponent (i.e. NTIME(22O(n))).
If MAE = NEE then MA = NEXP ∩ coNEXP [IKW01].
Contained in NEEXP.
Same as ZPP, but with 2O(n)-time instead of polynomial-time.
ZPE = EE if and only if ZPP = EXP [IKW01].