跳转到内容

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.