P-NP问题定义学习笔记

P问题即是多项式时间复杂度可以求解的问题,取多项式单词(Polynomial)的首字母。NP问题并不是不能在多项式时间复杂度内求解的问题,而是可以在多项式时间复杂度内验证一个解的问题。

多项式时间复杂度即是O(1),O(n),O(log(n)),O(n^a)等函数级别的时间复杂度。其它诸如O(n!),O(a^n)等函数级别的时间复杂度是非多项式的。随着问题规模的扩大,只有多项式时间复杂度的求解方法是在时间上可以接受的。为了说明什么是NPC问题,要先解释什么叫“约化(Reducibility)”。如果可以用求解问题B的方法求解问题A则说明问题A可以约化为问题B,意即问题A可以“变成”问题B。例如一元一次方程可以约化为一元二次方程,一个问题约化为另一个问题,时间复杂度增加了,问题的应用范围也增大了。通过对某些问题的不断约化,我们能够不断寻找复杂度更高,但应用范围更广的算法来代替复杂度虽然低,但只能用于很小的一类问题的算法。

我的理解是*“约化就是寻找更通用解的过程”*。

如果不断约化NP问题能够得到一个问题可以包含所有的NP问题,那这个问题就是NPC问题,即NP完全问题。NPC问题有很多,它们是一类问题。 P-NP问题也是著名的千禧年问题(Millennium Prize Problems)之一。

参考资料:

  1. What Is Big O? (Comparing Algorithms) (Undefined Behavior)
  2. 什么是P问题、NP问题和NPC问题 (Matrix67)
  3. P vs. NP - An Introduction (Undefined Behavior)
  4. Lecture 16: Complexity: P, NP, NP-completeness, Reductions (MIT Open Course)