E (計算複雑性理論)
計算複雑性理論において複雑性クラス E とは、決定性チューリング機械で 2O(n) の時間で解ける決定問題の集合である。これはすなわち、複雑性クラス DTIME(2O(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.
外部リンク 編集
- E at the Complexity Zoo
 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |