Class Description

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

Linked From

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


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