E（複雑性）

計算複雑性理論では、複雑性クラスEは、決定性チューリングマシンによって 2 ^O⁽ⁿ⁾の時間で解くことができる決定問題の集合であり、したがって複雑性クラスDTIME (2 ^O⁽ⁿ⁾ )と等しい。

E は、類似のクラスEXPTIMEとは異なり、多項式時間多対一還元に対して閉じていません。

他のクラスとの関係

EはNEに含まれる。

Allender, E.; Strauss, M. (1994)、「BPPへの応用を伴う小規模複雑性クラスの測定」、IEEE FOCS'94 論文集、pp. 807–818、ECCC TR94-004、DIMACS TR 94-18 。
Book, R. (1972)、「多項式時間で受理される言語について」、SIAM Journal on Computing、1 (4): 281–287、doi : 10.1137/0201019。
Book, R. (1974)、「複雑性クラスの比較」、Journal of Computer and System Sciences、3 (9): 213–229、doi : 10.1016/s0022-0000(74)80008-5。
Impagliazzo, R. ; Tardos, G. ( 1989)、「超多項式時間における決定問題と探索問題の比較」、IEEE FOCS 1989 会議録、pp. 222–227 。
渡辺修（1987）「多項式時間完全性概念の比較」、理論計算機科学、54（2-3）：249-265、doi：10.1016/0304-3975(87)90132-0。