E(複雜度)
這是此頁批准，以及是最近的修訂。
佇咧算複雜度理論內，複雜度類E代表一个決定型問題的集合，內底的問題會當使用確定型圖靈機佇兩 O ( n )，等於複雜度類 DTIME ( 二 O ( n ) )。
E佮相倚的類別 EXPTIME 無仝，佇咧多項式時間濟著歸約的時陣並無封閉。
參考資料
- Allender , E . ; Strauss , M . , Measure on small complexity classes with applications for BPP , Proceedings of IEEE FOCS'九十四 : 八百空七–八百十八 , 一千九百九十四 , Template : ECCC , DIMACS TR 九十四孵十八 .
- Book , R . , On languages accepted in polynomial time , SIAM Journal on Computing , 一千九百七十二 ,一( 四 ) : 兩百八十一–兩百八十七 .
- Book , R . , Comparing complexity classes , Journal of Computer and System Sciences , 一千九百七十四 ,三( 九 ) : 兩百十三–兩百二十九 .
- Impagliazzo , R . ; Tardos , G . , Decision versus search problems in super-polynomial time , Proceedings of IEEE FOCS 一千九百八十九 : 兩百二十二–兩百二十七喔 , 一千九百八十九 .
- Watanabe , O . , Comparison of polynomial time completeness notions , Theoretical Computer Science , 一千九百八十七 ,五十三: 兩百四十九–兩百六十五 .
外部連結
- _ Complexity Zoo _ : Class E