NE (複雜度)

計算複雜度理論內,複雜度類 NE是一個決定型問題的集合,包含能使用非決定型圖靈機,在O(kn) (k是某個常數)時間內解決的問題。

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

相關條目

參考資料

Prefix: a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9

Portal di Ensiklopedia Dunia

Kembali kehalaman sebelumnya