计算复杂性理论

计算复杂性理论

整体关系图


P 问题

是指在多项式时间内可以找出解的决策问题。

NP 问题

当给出决策问题的答案的时候 可以很容易（多项式时间内）验证该答案是正确的，那么这类决策问题就是 NP 的。

NP-hard 问题

NP-hard，指所有 NP 问题都能在多项式时间复杂度内归约到的问题。

NP-complete 问题

既是 NPhard 问题也是 NP 问题

P 与 NP 的关系

P 是 NP 的一部分。有意思的是想要证明 P=NP 这个问题本身就是一个 NP 问题。真是一环套一环，有点循环论证的味道了。

NPhard 与 NPC 与 NP 的关系

引入关于约化的概念，如果 A 问题可以用 B 问题来解决，那么就说 A 可以约化到 B，前提是 B 的时间复杂度必须比问题 A 高，因为如果 A 的问题比 B 还难，那就没有必要引入 A 问题。道理是：解决难的问题的方法总是可以用在解决简单的问题之上，但是解决简单问题的方法却不一定可以放在解决难的问题之上。

NPC 与 NP-Hard 的典型示例 - 旅行推销员问题

旅行推销员问题（Traveling Salesman Problem, TSP）是一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。

旅行商问题有两个版本：

1. 在一个图里，除了起始点以外不重复地遍历所有节点构成一条闭合回路，问这条回路的最短路径是多少？（应如何选择行进路线，以使总的行程最短）--- 这个是最优解问题
2. 在一个图里，除了起始点以外不重复地遍历所有节点构成一条闭合回路，问路径长度小于等于某个值的这样的回路是否存在？（应如何选择行进路线，以使总的行程小于等于某个值）--- 这个是判定性问题
   对于问题 1，是无法令确定型图灵机在多项式时间内验证答案的，所以问题 1 不是 NP 问题，因此也不是 NPC 问题，但是 Hamilton 回路问题可以约化为 TSP 问题，而 Hamilton 回路问题是 NP 问题，因此是 NP-Hard 问题。

对于问题 2，可以令确定型图灵机在多项式时间内验证答案，所以问题 2 是 NP 问题，同时 Hamilton 回路问题可以约化为 TSP 问题，而 Hamilton 回路问题是 NP 问题，因此问题 2 是 NP-Hard 问题，同时它也是 NPC 问题。