Class Description

EEXP: Double-Exponential Time

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

Also known as 2-EXP.

Contains EE, and is contained in NEEXP.

Linked From

2-EXP: Double-Exponential Time

See EEXP.

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


NEEXP: Nondeterministic EEXP

Nondeterministic double-exponential time (i.e. NTIME(22p(n)) for p a polynomial).

Equals MIPEXP (unrelativized).

More about...