跳转到内容

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以相同答案互相轉換的方法。

參考資料

  1. ^ Garey & Johnson (1979), p. 117, 120.