NP-易

在計算複雜度理論內，NP-易（或称“NP-容易”，NP-easy）這個複雜度類是使用帶有在NP裡面某個決定性問題神諭的圖靈機，能在多項式時間內解決掉的功能性問題。

換句話說，一個問題X屬於NP-易，若且唯若存在某個在NP裡面的問題Y，令X可以於多項式時間內圖靈歸約（polynomial-time Turing reducible）至Y。^[1]換句話說，給予一個解決Y的神諭（一個只需要單位時間就可以），則存在一個在多項式時間內解決X的演算法（可能需要藉由不斷的使用神諭，這是可以接受的）。

NP-易也是FP^NP（參見功能性問題頁面）或者FΔ₂P（參見多項式層級頁面）的別名。

一個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.