L19 - L20 NPC
Definition (The class NP)
NP is the class of decision problems that are solvable in Polynomial time by Non-deterministic algorithm.
P 问题： 对于一个问题，如果存在解决问题的多项式时间代价的算法，那么该问题称为 P 问题。
NP 问题： 如果一个问题的解在多项式时间内可以验证，则称为 NP 问题。可验证的意思是：非确定性地猜测该问题的任意一个解，在多项式时间内能够检测这个解是不是该问题的解。
NP 难问题： 如果对于任意的 NP 问题 Q，Q 都能多项式时间归约到问题 P，则称 P 为 NP 难问题。
NPC 问题： 一个问题既是 NP 问题，又是 NP 难问题，则它被称为 NP 完全问题。
Definition (Non-deterministic polynomial algorithm.)
Given an instance I of a decision problem: Guessing: generate a certificate c for $I$ Verifying: V( $I$ , c ) eg. INDEPENDENT-SET $\in$ NP
Proof
Given G= (V, E) and k:
- Guessing: Nondeterministically select a subset C of k vertices of G.
- Verifying: Test whether G contains no edges for all vertices pairs in c.
- Output: If the test passes, ouput "yes' '; otherwise, output' no' .
The complexity is O($n^2$).
已知，常用的NP问题B。B归约到C。
辨析
问题 1：归约的方向与 NPC 问题的证明
我一直感觉归约的方向有点反直觉。 或者说，我是因为看了教材上给的例子之后才觉得反直觉。
是这样一个例子（简化说明）： 划分问题：一个特殊问题 背包问题：一个一般问题 划分问题是背包问题的一个特例（或者说，把背包问题的某些参数确定后，就变成了划分问题）。 已知划分问题是 NPC 问题，证明背包问题也是 NPC 问题。
要证明一个问题 B 是 NPC 问题，做法就是：
- 证明问题 B 是一个 NP 问题。
- 按照定义证明即可
- 证明一个 NPC 问题 A 能够归约到问题 B（问题 A 的难度小于等于问题 B）
教材上说，把背包问题的某些参数确定后，就变成了划分问题，由此得到了「划分问题到背包问题的一个归约」。
看到这里我就有点懵了，我好像看不懂这中间的关系了，具体理清思路后是这样的： 1、A 问题归约到 B 问题，说明 A 问题的难度不高于 B 问题。 2、特殊问题比一般问题简单，所以特殊问题可以归约到一般问题。 3、这个问题里的归约是什么：是一般问题特殊化的过程。
我之前搞不懂，为什么「一般问题的特殊化」是一个「从特殊问题到一般问题的归约」？一直觉得这很反直觉，很矛盾。 后来才理解到，一般问题的特殊化的实质是：构造了一个从特殊问题的参数到一般问题参数的映射，这个映射正是从特殊到一般进行归约所需要的。
最后。 三色问题是四色问题的特例吗？是的。 所以三色问题其实比四色问题简单？对。 如何把三色问题归约到四色问题？把四色问题特殊化为三色问题即可。
问题 2：伪最大团与最大团问题的区别
伪最大团问题： 输入是图 G，有一个常数 k，问图 G 中是否存在大小为 k 的团？ 最大团问题： 输入是图 G 和参数 k，问图 G 中是否存在大小为 k 的团？
这两个问题的区别在于，前者的 k 是常数，后者是参数（输入、变量）。 结论告诉我： 1、伪最大团问题是具有多项式时间的解法，因此是 P 问题。 2、最大团问题，暂时没有人找到多项式时间算法，所以只是 NP 问题。
我使用暴力算法： n 个顶点中任选 k 个顶点，并遍历这 k 个顶点可能形成的所有边，总的时间复杂度是 $C(n,k)*\frac{k(k-1)}{2}$。
就是这个式子让我疑惑了。 我一看，左边组合数，分解后是阶乘，多项式，右边也是多项式。 诶？这不就是多项式时间吗？
不仅这两个问题的解相同，我又看到了书上的定理「最大团优化问题在多项式时间可解，当且仅当最大团判定问题在多项式时间可解」，我居然证明出了这个被称为 NPC 问题的最大团优化问题是一个 P 问题？！
理性让我知道自己肯定错了，这么简单的步骤还想破解世界难题？ 终于在与同学的一番讨论后我才明白错误的地方： 阶乘！ 我把 O(n!) 当成了多项式时间了！
而后再看暴力算法时间复杂度的式子，左边组合数分解后是阶乘除以阶乘，化简得到的是 n^k。 这个式子，对于伪最大团问题来说，k 是常数，所以是多项式时间；但对于最大团问题来说，k 是输入，它的规模是 O(n)，所以这个式子其实是 O(n^n)，不是多项式时间。
由此这个问题的疑惑变解开了。
由此引出下一个问题：
问题 3：伪多项式时间
有些问题的输入很特殊，你能很明确的确定输入的规模：n 个顶点，n 个数字 之类的。对于这些问题，多项式时间复杂度很好确定。 但对于那些多个输入的问题，或者说输入是一张图，信息很多，变量也很多，那你如何确定一个关于这些变量的式子是不是多项式时间呢？ 比如，输入有 n、k，我给的式子是 O(nk)、O(n^k)、O(k^2+n^2)等等，由于第二个问题已经讨论过，所以这几个还是比较好回答的。 但如果是更复杂的输入，似乎教材中并未给出清晰明确的「多项式时间」的定义。
由此引出一个概念： 伪多项式时间。
如果一个问题的 input size（输入规模或输入大小）为 x，某个解决这个问题的算法的最坏时间复杂度为O(x^k)，其中 x^k 表示 x 的 k 次方，此处 k 为已知常数，那么这个算法可以成为多项式时间算法。
什么是 input size？ 这个问题所有输入用二进制表示下的位数。
经典的伪多项式时间的问题：背包问题、素数判定问题。
知乎上看到这样一个解释： 算法的时间复杂度是输入数据的多项式表达，但却是输入数据长度的指数时间表达。
举个例子， 一问题的输入是一个整数 n，这个整数 n 的大小没有限制，也就是说可能不只是32位、64位等。 解决这个问题的算法的时间复杂度假设为 O(n^3)。 这个问题的输入规模 x = logn（即 n 对应于二进制下的 bit 位数）。 由此得到时间复杂度为 O(2^{3x})，这是一个指数型的代价，则该算法的代价实际上伪多项式时间。
而对比数组排序问题，每个数都是整数， 每次增加一个数，只增加 32 比特，所以原输入规模 x = 32n， 这个问题的算法就是多项式时间的。
分析出来的区别：数据规模。