P问题, NP问题, NP-hard问题, NPC问题

小知识

参考资料 : [Styx]P问题，NP问题，NP-hard问题，NPC问题，傻傻分不清楚？

P问题 和 NP问题

时间复杂度

多项式时间复杂度 : 如 $O(n), O(logn), O(n^2)$.

非多项式时间复杂度 : 如 $O(2^n),O(n!)$ 这一类 数据规模 $n$ 在指数位置的复杂度.

P问题

定义

能够在多项式时间复杂度内解决的问题, 称为 P问题(Polynomial problem).

NP问题

首先注意, NP问题并不是所有不是N问题的问题 (有点绕).

因为现在没有多项式解法的问题, 在未来不一定没有多项式解法, 所以除了那些已经被证明了不存在多项式解法的问题, 其他问题在未来都可能变为P问题.

而一个问题没有多项式解法的条件是 : 不能在多项式复杂度内检验它的一个解.

定义

它的一个解能在多项式复杂度内检验的问题, 称为 NP问题(Non-Deterministic Polynomial Problems).

其中 "Non-Deterministic" 是 "非确定性" 的意思.
所以, NP问题实际上是无法判断它不是 P问题的问题.

而对于一个P问题, 它既然能在多项式复杂度内解决, 那也一定能在多项式复杂度内检验它的一个解, 所以我们可以得到

NP-hard问题 和 NPC问题

前置知识 : 归约

归约指的是将A问题进行归约后可以用B问题的解决方法解决，也就是把A问题变成B问题解决.

NP-hard问题

如果有一个问题可以使所有NP问题在多项式复杂度内归约到它，那么它就是NP-hard问题

例如 停机问题

NPC问题

如果有一个NP问题可以是所有NP问题在多项式复杂度内归约到它, 那么它就是NPC问题

其中 "C" 表示 "Complete", 所以NPC问题也被称为 "NP完全问题".

由它们的定义, 我们可以知道, NP-hard问题是不一定有解的, 例如上面的"停机问题",
但NPC问题是有可能有多项式解法的, 所以, 只要解决了一个NPC问题, 就可以解决所有的NP问题, 也就可以解决世纪难题 : "P=NP?".

常见的NPC问题有3-SAT问题，旅行商问题等等.