NP-易
(重定向自NP-容易)
在計算複雜度理論內,NP-易(或称“NP-容易”,NP-easy)這個複雜度類是使用帶有在NP裡面某個決定性問題神諭的圖靈機,能在多項式時間內解決掉的功能性問題。
換句話說,一個問題X屬於NP-易,若且唯若存在某個在NP裡面的問題Y,令X可以於多項式時間內圖靈歸約(polynomial-time Turing reducible)至Y。[1]換句話說,給予一個解決Y的神諭(一個只需要單位時間就可以),則存在一個在多項式時間內解決X的演算法(可能需要藉由不斷的使用神諭,這是可以接受的)。
NP-易也是FPNP(參見功能性問題頁面)或者FΔ2P(參見多項式層級頁面)的別名。
一個NP-易的例子是將一堆字串進行排序。決定型問題"字串A是否比B來的大"是一個NP問題。然後我們已經有快速排序(quicksort)或者合併排序(merge sort)這些演算法,它們只要有單位時間比較大小的方式,即可以在多項式時間之內排序一個集合。因此我們結合以上兩點可以得知,字串排序是NP-易的問題。
NP-易裡面也是有非常困難的問題。例如說,可以參考NP-等價(NP-equivalent)頁面裡面的例子。
NP-易的定義上使用圖靈規約而非多對一歸約(many to one reduction),因為Y是決定型問題,答案只有TRUE或者FALSE,但是問題X是功能性問題,答案可以有很多種。因此,並不存在一個將X跟Y以相同答案互相轉換的方法。
參考資料
- ^ Garey & Johnson (1979), p. 117, 120.
|