不知道你有没有听说过 \(P = NP\) 问题，反正我总是听到这个。和这个问题相关的还有P、NP、NP-hard、NP-complete这些概念。这学期上了算法课，终于理解了这件事情（吧）。在这里分享一些自己的想法。
这学期上算法课，讲到了一个叫做归约的概念，英文叫reduction：假设现在有个问题B，很难，我们不知道怎么解决，但是我们知道怎么解决问题A，那我们就想一想能不能把问题B转化成问题A，然后解决问题A，得到问题A的解之后再想办法转回来变成问题B的解。这样就可以解决问题B了。
如果这个方法可行，那么这时候可以说，问题A可以归约到问题B，写作
这个长得很像小于等于号，这是有 原因的 ，反映了问题A和问题B之间难度的关系。
这个套路其实我们一直都在用，我第一个想达到的例子就是有些三维几何题做不出来的时候，可以建一个坐标系，然后用代数方法来证明。在这个例子里面，转换关系是这样的
那这里面就有个很自然的问题啊，你凭什么说我建坐标系之后证明的是对的呢？这个问题我们经常忽略，因为通常内层问题（问题A）和外层问题（问题B）差别不会太大，或者我们早就下意识认为建坐标系来解几何题是很自然的、不可能出错的。但是上算法课每次做归约的时候，外层问题和内层问题都长得看上去完全不一样、完全不是一类问题，根本不可能想到一个问题怎么就莫名其妙就能归约到另一个问题。
举个例子，考虑两个问题，第一个问题是著名的背包问题：
有一个最大承重是 \(M\) 的背包，有 \(n\) 件物品，第 \(i\) 件物品的重量是 \(w_i\) 、价值是 \(v_i\) ，能否巧妙的选取物品放入背包，使得背包里的所有物品重量总和不超过最大承重 \(M\) ，同时所有物品的价值总和不小于 \(\theta\) ？
第二个问题叫subset sum、子集和的问题，也是个很著名的问题：
给一个数字集合 \(U\) 和一个目标数字 \(t\) ，问是否存在一个 \(U\) 的子集 \(U'\) ，使得 \(U'\) 的累加和正好是 \(t\) 。
假设现在我们有背包问题的多项式阶算法了，能不能顺便解决一下subset sum问题呢？可以的哦 [1] 。
先不要看答案，感受一下，是不是很难想？如果你想出来了，那你也太聪明了，再试试3-SAT归约到哈密尔顿回路？
对这种问题，归约就不能瞎想、想当然觉得是对的就是对的了。给出归约的思路的时候，还需要证明这样归约是对的。想想我们在归约的时候做了哪些事情
做了两件事情
把外层问题实例 \(x\) 转化成了内层问题实例 \(x'\)
这一步有点复杂，你得想一想。想出来还不一定对，哈哈。
把内层问题的解 \(y'\) 转化成了外层问题的解 \(y\)
这一步很简单，因为在上面的例子里，内层问题和外层问题的返回值都是布尔类型，要么是T要么是F，所以这里可玩的花样很少
要么内层返回T的时候、外层也返回T，并且内层返回F的时候、外层也返回F
要么内层返回F的时候、外层返回T，并且内层返回T的时候、外层返回F
不会有其他的情况，比如“内层返回T的时候、外层返回T，并且内层返回F的时候、外层也返回T”，那这种是不可区分的：什么时候外层返回F呢？这侧面说明了你的归约有问题，它只能解决部分问题，只能解决外层是T的那些问题，这是不允许的，归约必须解决这个问题的全部，不能只解决一部分。
其实这两种都是等价的，第二种的话，内层取个反不就和第一种一样了？肯定是“内T外T、内F外F”更自然一点，所以就用第一种吧。
这样的话， \(h\) 这个算法就极其简单了，就是个复读机，直接把内层的输出拿过来变成外层的输出，所以这里没什么需要证明的。整个归约正确与否，完全取决于第一步外层输入到内层输入的这个算法 \(g\) 了。
那要证明 \(g\) 正确怎么证呢？也很简单的，就是证明算法的正确性嘛。算法的正确性怎么证明？假设世界上已经有一个正确的神秘算法 [2] 能解决外层问题了，那么我们要证的就是，对于任意一个外层问题实例，神秘算法给出的结果和通过归约给出的结果相同，这不就证明了正确性吗 [3] ？分情况讨论一下
内层输出T（这时复读机 \(h\) 让外层也输出T）、神秘算法也输出T
内层输出F（这是复读机 \(h\) 让外层也输出F）、神秘算法也输出F
从“问题A能被归约到问题B”这件事情，我们不仅能解决问题A，还能获得额外的信息。这个额外的信息，我理解为“问题A的难度小于等于问题B的难度”。
这其实很显然 [5] ：想象一下，因为你能解决问题B，所以你能制造出一种机器来解决问题B、或者你能写代码让电脑能解决问题B——不管用什么方式，总之世界上能产生一种具有解决问题B能力的机器（或者人）——显然的事情是，无论是机器还是人，都没办法做超出自己能力范围的事情，也就是说，没办法保证能解决难度大于自己已经会解决的问题的难度的那些问题。
那可能有人会说了，飞机能飞，人不能飞，飞机不能思考，但是人能思考，那么到底是飞机的能力更大呢还是人的能力更大呢。这种情况下，就要讨论能力的定义了，如果各种能力之间是有序的，那么确实能区分出飞机和人到底哪个能力更大。这里不讨论这个问题。这里提 能力 只是为了让你有一个直观理解：能力越大，能解决的问题越难。
还有一件事情是，如果这个机器能解决问题A，那有没有可能这个机器其实能力不止能解决问题A这个难度级别的问题呢？有没有可能这个机器实际上能解决比问题A更难的问题？是有可能的，但是你没法保证。一个原则是，观测多少、说多少话。当你发现这个机器能解决问题A的时候，你就只能说这个机器能解决难度不超过问题A的问题，至于这个机器到底能不能解决比问题A还要难的那些问题，你需要再证明确实这个机器能解决比问题A更难的问题才行。有点像阿贝尔幂级数收敛定理，当你发现幂级数在 \(x_0\) 处收敛的时候，你只能说幂级数在 \(|x| < |x_0|\) 的范围内都收敛，但有可能这个幂级数其实在 \(x_0 + 1\) 处也收敛。
所以可想而知，如果把世界上一切的问题都放在一个集合里，这个集合是可以按照问题难度来建立顺序的。就像把所有的实数放在一个集合里，因为实数可以比大小，所以实数集就可以具有某种结构，从而变成数轴一样。问题集合也具有这种结构。
如果之前听说过背包问题，会发现刚才提 背包问题 的时候，问题的表述有点奇怪：
有一个最大承重是 \(M\) 的背包，有 \(n\) 件物品，第 \(i\) 件物品的重量是 \(w_i\) 、价值是 \(v_i\) ， 能否 巧妙的选取物品放入背包，使得背包里的所有物品重量总和不超过最大承重 \(M\) ，同时所有物品的价值总和不小于 \(\theta\) ？
怎么你在别处听说过的背包问题是像下面这样写的呢？
有一个最大承重是 \(M\) 的背包，有 \(n\) 件物品，第 \(i\) 件物品的重量是 \(w_i\) 、价值是 \(v_i\) ， 怎样 巧妙的选取物品放入背包，使得背包里的所有物品重量总和不超过最大承重 \(M\) ，同时所有物品的价值总和尽可能最大？
甚至你有可能还听说过这种
有一个最大承重是 \(M\) 的背包，有 \(n\) 件物品，第 \(i\) 件物品的重量是 \(w_i\) 、价值是 \(v_i\) ，选取物品放入背包，在保证背包里的所有物品重量总和不超过最大承重 \(M\) 的同时，背包里所有物品价值总和的 最大值 是多少？
这三个问题看起来很相似，但是看上去又不太一样，问题的解的类型就不一样
对第一个问题，你的回答是“能”或者“不能”，所以第一个问题的解是布尔类型的，T表示能、F表示不能
对第二个问题，你的回答是哪些物品，所以第二个问题的解是集合类型的，是使得背包价值总和最大的一组物品的编号
对第三个问题，你的回答是那个最大值，所以第三个问题的解是数字类型的，是背包价值总和的最大值
这三个问题之间难度关系是怎样的呢？直观上，你会感觉第二个问题比第三个问题难，因为当你在第二个问题里面得到了那组能使背包价值总和最大的物品编号之后，把这些物品的价值加起来，就得到了第三个问题的解，所以显然第三个问题可以用第二个问题来解
直觉还会告诉你第三个问题好像比第一个问题难，因为当你得到第三个问题里的那个价值最大值之后，把这个最大值和第一个问题里的 \(\theta\) 比较一下，如果发现 \(\theta\) 大于那个最大值，那么显然第一个问题是F；如果发现 \(\theta\) 小于等于那个最大值，那么显然我永远都可以给背包里装价值最大的那个组合，使得背包价值总和等于最大值，从而大于等于 \(\theta\)
第一个问题和第二个问题就更不用说了，肯定是第二个问题更难嘛：你直接解决第二个问题，得到那个最优组合，算下价值总和，和 \(\theta\) 比较一下不就好了？
所以直觉告诉我们，第二个问题最难，第三个问题中，第一个问题最简单。
好的，反直觉的来了。你再仔细想想，能不能用第一个问题解决第三个问题呢？也就是说能不能把第三个问题归约到第一个问题？是可以的，用二分。
首先，背包的价值总和不可能大于所有待选物品的价值总和吧？那可以把初始上界 \(r\) 定为这个值；背包的价值总和不可能小于0吧？那可以把初始下界 \(l\) 定为这个值。然后不停地二分搜索，每次迭代都设 \(\theta = {l + r \over 2}\) ，执行一次问题1，会出现两种情况
如果问题1说存在的，那么最大值一定在 \(\left[{l + r \over 2}, r\right]\) 之间，这时候设 \(l := {l + r \over 2}\) ，继续迭代
如果问题1说不存在，那么最大值一定在 \(\left[l, {l + r \over 2}\right]\) 之间，这时候设 \(r := {l + r \over 2}\) ，继续迭代
因为电脑的浮点数运算精度有限，所以在迭代了 \(O(\ln n + \ln \max\{v_i\})\) 次之后， \(l\) 会等于 \(r\) 。这就是最大值了。
所以第三个问题可以归约到第一个问题，也就是说
因为之前直觉已经有 \(P_1 \leq_p P_3\) 了，所以 \(P_1\) 和 \(P_3\) 可以互相归约、难度相等。
那第二个问题和第三个问题呢？能不能用第三个问题解决第二个问题？或者说，能不能已知背包里所有物品价值总和的最大值之后，反推出哪些物品被装进背包了？
当然可以啊，我觉得这个比1和3甚至更容易想到，只要一个物品一个物品测试就好了：
去掉第一件物品，跑一下问题3，如果发现那个最大值变小了，说明第一件物品是应该要选的；如果发现那个最大值没变化，说明第一件物品不选
去掉第二件物品，跑一下问题3，如果发现那个最大值变小了，说明第二件物品是应该要选的；如果发现那个最大值没变化，说明第二件物品不选
…
因为总共有 \(n\) 个物品，所以总共要调用问题3一共 \(n\) 次。所以第二个问题也可以归约到第三个问题
忘了说了，归约是有传递性的，如果问题1可以归约到问题2、问题2可以归约到问题3，那么说明问题1也可以归约到问题3
这个也很显然（又显然了），问题1可以用问题2解决、问题2可以用问题3解决，那当然问题1可以用问题3解决。
所以为什么没有发明 \(=_p\) 这个记号呢……
既然这三个问题难度相等，而且都是在背包这个背景下的，所以我倾向于认为这三个问题其实是同一个问题的三个版本、或者表象——第一个问题是判定版本、第二个问题是找解版本、第三个问题是找最值版本。
有些问题是没有这三个版本的，有可能只有其中的两个版本，比如 3-SAT 和 circuit-SAT问题，只有判定版本（是否存在一个 \(\mathbf{z}\) 的取值使得布尔函数 \(f(\mathbf{z}) = T\) ）和找解版本（找到一个 \(\mathbf{z}\) 的取值使得布尔函数 \(f(\mathbf{z}) = T\) ），而没有找最值版本。这是由问题的本征属性决定的。
因为这三个版本难度相同，所以在归约的时候，不妨都选取外层问题的判定版本和内层问题的判定版本。这样解的构造算法 \(h\) 就非常简单了，就是个复读机：只要内层问题返回T、外层问题就返回T；内层问题返回F、外层问题也返回F。
而且很作弊的一点是，虽然我们证明的是判定版本能归约到判定版本，但是你在证明的时候，是可以用找解版本的解的哦！换句话说，你在知道内层问题返回T的同时，还自动知道了到底是哪个解让内层问题返回T、内层问题的极值（如果这个问题有找极值版本的话） [4] 。
\(A \leq_p B\) 中小于等于号右下角的 \(p\) 实际上是polynomial也就是多项式的意思。这是什么意思呢？
刚才subset sum归约到背包问题的例子里面，只解决了一次内层问题，或者说，外层问题实例只转化了一次。从“机器”这个角度说，就是这个机器只跑了一次、解决了一个内层问题，然后经过最后的转换之后，我们就得到了外层问题的解。
其实也是可以转化成多个内层问题实例、让内层机器跑多次才能得到答案的。只要让内层机器跑的次数也是多项式阶次数就好了。
这里要说明一下，所谓的多项式阶数复杂度，是指复杂度的表达式只和输入的 规模 有关，而不是和输入的 值 有关。比如假设 \(n\) 是物品的个数、 \(M\) 是背包最大承重， \(O(n)\) 就是多项式阶的，但是 \(O(n M)\) 不是多项式阶，而是 伪多项式阶 ，因为复杂度里出现了输入的值 \(M\) 。
然而，如果是 \(O(n \ln M)\) 的话，那么这个又确实是多项式阶了。这是怎么回事呢？是因为虽然 \(M\) 不是输入规模，是输入的值，但是 \(\ln M\) 确实是输入规模。先别打我，这是千真万确的事情，我第一次知道的时候也很惊讶，但是随后一想，发现真的是这么回事。想一想，电脑要存储 \(M\) 这个数字需要多少空间？就假设 \(M\) 是个整数，在现在的二进制电脑里，需要 \(\log_2 M\) 个bit来存储，这是不是一种输入 规模 呢？
那假设问题A归约到问题B只要单次归约、问题C归约到问题B却需要多次归约，是否说明问题C比问题A [7] 更难呢？不一定，有可能问题A、B、C的难度是相等的。比如刚才找最值规约到判定的那个例子，是多次归约，但是这两个问题（或者版本/表象吧）难度相等。
终于要说回这个了。集合里面经常喜欢做一件事情，就是给一个大集合过滤，把满足某些条件或者条件的元素挑出来开小灶、放到单独的一个集合里。比如把复数集里的实数挑出来，变成实数集，这样本来复数集是没法比大小的，放到了实数集里，就可以比大小了。
那同样可以对 问题集合 做同样的事情，把满足某些性质的问题挑出来。最先挑出来的当然是那些有多项式阶算法的问题。这些问题，我们把它们放到一个叫做 P 的集合里。P是polynomial、多项式的意思。
那剩下的哪些很难的问题怎么办？继续细分。我们发现，有些问题，想要找到那个解很难，但是如果你有一个答案（不管是蒙的猜的还是怎么着得到的），想验证这个答案是否是这个问题的解很容易。这里的难，是指至今没有发现多项式阶算法的难；这里的容易，是指存在多项式阶的算法。
再次考虑刚才说到的subset sum、子集和问题：
给一个数字集合 \(U\) 和一个目标数字 \(t\) ，问是否存在一个 \(U\) 的子集 \(U'\) ，使得 \(U'\) 的累加和正好是 \(t\) 。
这个问题至今都没有发现多项式阶算法，只能用暴力算。想想一个大小是 \(n\) 的集合，总共有 \(C_n^0 + C_n^1 + ... + C_n^n = 2^n\) 个子集！所以暴力地、穷举每个子集、再算出每个子集的累加和这种做法的复杂度是 \(O(2^n)\) ，它不是多项式阶的。
可是这个问题很容易验证啊！给一个集合 \(X\) ，要验证这个集合是否是问题的解很简单，两步
检测 \(X\) 里的每个元素是否都是 \(U\) 的元素
如果 \(X\) 里存在某个元素不是 \(U\) 的元素的话， \(X\) 肯定不是 \(U\) 的子集了。
把 \(X\) 里面的数字都加起来，得到累加和，看看是否等于 \(t\)
如果等于 \(t\) ，那么恭喜， \(X\) 是问题的解；如果不等于，那就不是问题的解。
如果 \(X\) 的大小是 \(m\) 的话，第一步的复杂度是 \(O(m)\) ，因为判断一个元素是否在一个集合里的复杂度最低是 \(O(1)\) ；第二步的复杂度还是 \(O(m)\) ，只需要遍历一遍 \(X\) ，记下和就好了。所以总的复杂度是 \(O(m)\) ，是多项式阶的。
所以我们对于类似subset sum这样的问题，用“是否存在多项式阶的验证算法”这个性质来过滤。把所有容易验证答案的问题，放到一个叫做 NP 的集合里面。NP这个名字我很不喜欢，因为意思是non-polynomial，但是NP集合里面的问题不需要满足“不存在多项式阶算法”的性质，所以NP其实如果叫easy-validateable说不定更好？
思考一下P集合和NP集合的关系，显然P集合是NP集合的子集。因为P集合里的任意问题都有多项式阶算法来 解决 ，所以没有理由不存在多项式阶算法来 验证 啊。从直观上想，验证一个答案是否是问题的解肯定难度不会超过找到问题的解吧！大不了，我先找到这个问题的解（说不定还不止一个，那就放到一个解集合里），然后看答案是否在解集合里不就好了？
这就是我不喜欢NP这个名字的一个重要原因，NP集合里的问题，并不是“存在高效验证算法、还没找到高效找解算法”的问题，而是只需要满足“存在高效验证算法”就可以了。千万别搞混了。另外，如果你证明了存在“存在高效验证算法、不存在高效找解算法”的问题，其实间接证明了 \(P \neq NP\) 了。恭喜你 发财了 。
刚才说了问题集合能按照难度来比大小。那么很自然的问题是，NP集合的上界是开边界、还是闭边界呢？
想想区间 \([1, 2]\) 和 \([1, 2)\) ，2都是这两个区间的右边界，但是2在第一个区间里，不在第二个区间里。
同样的，NP集合里，是否存在一个 最难的问题 ？有没有可能NP集合其实是像 \([1, 2)\) 那样子，存在一组无限接近最难问题的问题，但就是不存在那个实边界呢？
用定义、也就是归约来描述，如果存在最难问题，就等于说是NP集合里任意一个问题X，都能归约到这个最难的问题Y
直接上结论：存在的。而且这样的问题不止一个，它们可以互相两两归约，所以难度相等；因为可以互相归约，所以一旦哪天找到了其中某一个问题的高效找解算法，其他问题都自动解决了，而且NP集合里所有的问题都解决了，因为你已经解出了最难的问题，没理由不能解决难度相当、或者难度更低的问题。
这些“最难的问题”，就是所谓的NP-complete问题。complete这个词用的特别恰当，完全，表示的就是解决了我们，就解决了NP里的一切问题。
那NP-hard呢？NP-hard表示的是，难度不小于NP-complete问题的那些问题。也就是说如果问题X是NP-complete问题，如果问题X能归约到问题Y
说明问题Y的难度大于等于问题X的难度。
显然所有的NP-complete也是NP-hard问题，因为所有的NP-complete问题难度都相等，满足那个“不小于”的关系。
甚至我们还发现，NP-complete这个集合，其实就是NP-hard集合和NP集合的交集。不过是先有NP-complete才有NP-hard，所以这个好像也没什么意义……
那么存不存在不是NP-complete的NP-hard的问题呢？存在的，比如围棋，你没法高效验证这一步下这个子是全局最优解。顺便说下Alpha Go是怎么做的，它用深度学习搞了个估值网络，然后把子下在估值最高的那个格子里。即便是这样，它还是输给李世乭一局，所以显然这个估值网络没法给出全局最优解。
如果想要证明 \(P = NP\) ，思路肯定是找到某个NP-complete的高效找解算法，不用多，一个就够了，反正可以互相归约。然而找不到。可是找不到不代表不存在啊，可能只是你太笨了呢？
如果想要证明 \(P \neq NP\) ，思路其实刚才已经在发财那里提到过了，找到一个“存在高效验证算法、但不存在高效找解算法”的问题就够了。这个感觉比证明 \(P = NP\) 还要难，不仅要找到这种奇葩问题，还要证明不存在高效找解算法。这个不存在就很证明啊。你要证明存在，找出一个就行了，可是想要证明不存在，这怎么证。
那这样两边都没法证，只能在这里僵住。
如果真的有 \(P = NP\) ，那么这个还说明了一件重要的事情。刚才说过
所以很自然P是NP的子集。如果 \(P = NP\) ，那么NP和P互为子集，也就有
所以和 \(P = NP\) 等价的命题是，验证和找解难度相等。但是从直观上想，找解怎么可能和验证是同样难度的事情呢？所以这也是现在基本上大家都认为 \(P \neq NP\) 的重要原因。
既然找NP-complete问题的精确解很难、找不到，那不如退而求其次，找到相对来说不那么坏的解也不错。这就是很多近似算法的思路：我不去追求最优解了，但我能在多项式阶时间里，给你 保证 一个不差于最优解多少倍的近似最优解。
这个系数可以是常数，比如2（出现在欧几里得空间 [6] 中的旅行商人问题里）；还可以是 \(1 + \epsilon\) 这种可以任意逼近的（出现在实数背包问题里），叫 PTAS 。 \(\epsilon\) 有点像是你可以任意选择的精度， \(\epsilon\) 越接近0，近似解越好、越接近全局最优解。当然可想而知这肯定是有代价的，代价就是 \(\epsilon\) 越小，时间复杂度越高。但不管 \(\epsilon\) 是多少，算法都是多项式阶的，当然 \(n^{1000}\) 也是多项式阶的，但在 \(n\) 很小的时候，不见得比 \(2^n\) 快。这其中的利弊就需要你自己去权衡啦。
近似算法我不谈了……自己学的也不好。_(:з」∠)_
这里真的还有巨多我不明白的问题。比如算法课最后还讲到了NP-complete问题之间也有区别，有些NP-complete能够有任意逼近算法（比如欧几里得空间中的旅行商人问题），但有些NP-complete问题没有任意逼近算法（一般图中的旅行商人问题）。没有任意逼近算法的NP-complete是否能说是难度更大呢？还是说没有任意逼近算法的揭示了难度的另一个维度、另一种难度？可能这就是没有发明 \(=_p\) 记号的原因？
不管了，下午出分了，好像运气好的话还能拿个A，嘻嘻。
2019/12/16
啊出分了，拿了个B_(:з」∠)_苍天饶过谁。总算这学期最难的课过去了（但也留下了无数的问题啊）
2019/12/16