|
|
| 1行目: |
1行目: |
| − | [[計算複雑性理論]]において、[[複雑性クラス]] '''E''' とは、[[チューリングマシン|決定性チューリング機械]]で 2<sup>[[ランダウの記号|O]](n)</sup> の時間で解ける[[決定問題]]の集合である。これはすなわち、複雑性クラス [[DTIME]](2<sup>O(n)</sup>) に等しい。
| + | {{テンプレート:20180815sk}} __NOINDEX__ |
| − | | |
| − | '''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 [http://eccc.uni-trier.de/eccc-reports/1994/TR94-004/ TR94-004], DIMACS [http://dimacs.rutgers.edu/TechnicalReports/abstracts/1994/94-18.html 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.
| |
| − | | |
| − | == 外部リンク ==
| |
| − | * [http://qwiki.caltech.edu/wiki/Complexity_Zoo#e E] at the Complexity Zoo
| |
| − | {{Computer-stub}} | |
| − | | |
| − | [[Category:計算複雑性理論]]
| |
| − | [[Category:数学に関する記事]]
| |