随便说点
好久没写文章了，眼看今年就快过去一半了。
上次发的博客还是凑数的课程实验报告，笑。
今年上半年因为疫情原因，在家呆了好几个月，这学期学校也不准备开学了。
在学校，尤其是机房、教学楼和图书馆，有学习的氛围，周围的人都在学习，你会不由自主地也沉迷学习中。
然而在家就不一样了，效率完全看个人自控能力，像我这种控制不住就刷上 b 站知乎了的，这个学期的学习质量堪忧。唯一有点长处的是，这学期认真的记了笔记，放在了语雀上。
以后笔记都在语雀上了，服务器上的笔记网站就要关掉了。
服务器的乐趣就是折腾，我也折腾过不少，现在看来服务器对我还不是刚需。所以今年到期后可能就不再租了，同时博客应该会挂在 coding 或者 GitHub Pages 上，访问速度可能会有所下降，不过影响不大，反正大部分访问量都是我自己。
跑题了，拐回来。
我为什么会选择写 P、NP、NPC 问题呢？
因为最近算法课学到了这里，而且这里有一些「未解之谜」，最重要的是，我连着好长时间搞不懂其中的一些问题，经过了长时间讨论分析，最终有点领悟，下面就记录一下我的理解吧。
三种问题的定义
摘自我自己的笔记
P 问题：
对于一个问题，如果存在解决问题的多项式时间代价的算法，那么该问题称为 P 问题。
NP 问题：
如果一个问题的解在多项式时间内可以验证，则称为 NP 问题。可验证的意思是：非确定性地猜测该问题的任意一个解，在多项式时间内能够检测这个解是不是该问题的解。
NP 难问题：
如果对于任意的 NP 问题 Q，Q 都能多项式时间归约到问题 P，则称 P 为 NP 难问题。
NPC 问题：
一个问题既是 NP 问题，又是 NP 难问题，则它被称为 NP 完全问题。
我遇到的问题
问题 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，
这个问题的算法就是多项式时间的。
分析出来的区别：数据规模。