
_START_ARTICLE_
E (計算複雑性理論)
_START_PARAGRAPH_
計算複雑性理論において、複雑性クラス E とは、決定性チューリング機械で 2 の時間で解ける決定問題の集合である。これはすなわち、複雑性クラス DTIME(2) に等しい。_NEWLINE_E は類似のクラス EXPTIME よりも理論上の重要性が低いとされる。それは、多項式時間多対一還元において閉じていないためである。