E (計算複雑性理論)

計算複雑性理論において複雑性クラス E とは、決定性チューリング機械で 2^O(n) の時間で解ける決定問題の集合である。これはすなわち、複雑性クラス DTIME(2^O(n)) に等しい。

E は類似のクラス EXPTIME よりも理論上の重要性が低いとされる。それは、多項式時間多対一還元において閉じていないためである。

参考文献

E. Allender and M. Strauss. Measure on small complexity classes with applications for BPP, Proceedings of IEEE FOCS'94, pp. 807-818, 1994. ECCC TR94-004, DIMACS TR 94-18.
R. Book. On languages accepted in polynomial time, SIAM Journal on Computing 1(4):281-287, 1972.
R. Book. Comparing complexity classes, Journal of Computer and System Sciences 3(9):213-229, 1974.
R. Impagliazzo and G. Tardos. Decision versus search problems in super-polynomial time, in Proceedings of IEEE FOCS 1989, pp. 222-227, 1989.
O. Watanabe. Comparison of polynomial time completeness notions, Theoretical Computer Science 53:249-265, 1987.