跳至內容

E (複雜度)

維基百科,自由的百科全書

計算複雜度理論內,複雜度類E代表一個決定型問題的集合,裡面的問題可以使用確定型圖靈機在2O(n),等於複雜度類DTIME(2O(n))。

E與相近的類別EXPTIME不同,在多項式時間多對一歸約時並不封閉。

參考資料

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

外部連結