P=NP? (Easy Version)

这篇文章试图用较为简单的方法

解释什么是 P 问题、NP 问题、NPC 问题 和 NP-Hard 问题。

更为严谨的解释，将在 Hard Version 中描述。目前还在咕咕咕中。

---

什么是 NP 问题？

• \(\mathtt{P}\) ：能在多项式时间内解决的问题。

• \(\mathtt{NP}\) ：不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证的问题。

• \(\mathtt{NPC}\) ：即 NP 完全问题。

  所有 NP 问题在多项式时间内都能约化到它的 NPC 问题。

  因此解决了 NPC 问题，所有 NP 问题也都得到解决。

• \(\mathtt{NP-Hard}\) ：NP 困难问题。所有NP问题在多项式时间内都能约化到它的问题（不一定是NP问题）。

---

多项式时间

简单来说，如果存在正数 \(k\) 使得一个算法时间复杂度为 \(\mathcal{O}(n^k)\) （渐进上界记号），其中 \(n\) 为问题规模（输入的长度），则称这个算法是多项式时间的。

多项式时间的一些常见例子如 \(\mathcal{O}(1),~\mathcal{O}(n),~\mathcal{O}(n^2),~\mathcal{O}(n \log n)\) 等。

---

约化

约化(Reducibility)，简单的来说，问题 A 可以被约化为问题 B ，则说明用问题 B 的解法可以解决问题 A 。

打个比方，如果我说能在 \(\mathcal{O}(n^3)\) 的时间内求出 \(n\) 元一次方程组的解（问题 B）

而我现在要算一个二元一次方程组（问题 A），则显然可以直接套用问题 B 的解法。

花絮：其实这个算法就是 Gauss 消元法

同时也可以看出几个明显的性质：

1. 约化具有传递性。如果我能够求解三元一次方程，那我也能用类似的方法解出二元一次方程的解。
2. 约化后的问题更为广泛，但是复杂度不小于约化前的问题。
3. 约化前的问题较为局限，但是复杂度不大于约化后的问题。

---

进一步的解释

P 问题

P 问题，也是 OI 中最常见的问题，也就是能在多项式时间内解决的问题。

比如常见的最短路等算法，以及各种数据结构维护信息的题目等，就是 P 问题。

NP 问题

NP 问题是指可以在多项式的时间里验证一个解的问题。

通常情况下，找到一个解要花费的时间远大于验证一个解的时间。

目前解决 NP 问题的常用方法就是搜索算法和 DP 。

注意 DP 虽然有多项式的时间复杂度，但是这个复杂度是伪多项式时间的。

例如，背包问题是 NPC 问题，它有基于动态规划的伪多项式时间的解法（详见 Hard Version）

还有一个比较易于理解的例子。

假设你参加了一个比赛。这时你的同学告诉你，选手中有一个你认识的人。

如果他告诉你，那个人坐在后门那里，你只要瞟一眼就能确定你认不认识他了。（验证解）

但是如果他没告诉你，你就只能环顾四周，判断每一个人是不是你认识的。（寻找解）

NPC 问题

NPC 问题的定义非常简单。同时满足下面两个条件的问题就是 NPC 问题。

1. 它是一个NP问题。

2. 所有的NP问题都可以约化到它。

经典的 NPC 问题有 TSP 问题、逻辑电路问题等。

NP-Hard 问题

NP-Hard 问题满足 NPC 问题定义的第二条但不一定要满足第一条，即所有的NP问题都可以约化到它。

NP-Hard 问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是 NP 问题。

即使 NPC 问题发现了多项式级的算法，NP-Hard 问题有可能仍然无法得到多项式级的算法。

事实上，由于 NP-Hard 放宽了限定条件，它将有可能比所有的 NPC 问题的时间复杂度更高从而更难以解决。

P=NP?

即 P=NP 或 P≠NP 。这是一个暂未得到证明的难题。

多数计算机科学家相信 P≠NP 。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了（Karp的21个NP完全问题，在最早发现的一批中，有所有著名的已经存在的问题）。进一步地，P = NP这样的结果会导致很多惊人的结果，那些结果现在被相信是不成立的，例如 NP = 反NP 和 P = PH 。

---

参考文献：

[1] https://blog.csdn.net/huang1024rui/article/details/49154507

[2] https://oi-wiki.org/misc/cc-basic/

[3] https://zh.wikipedia.org/wiki/NP%E5%9B%B0%E9%9A%BE

[4] https://zh.m.wikipedia.org/wiki/%E5%A4%9A%E9%A0%85%E5%BC%8F%E6%99%82%E9%96%93