计算复杂性读书笔记（二）： 论怎么把一个证明写得有意思
比特猪
首先是版权声明，版权归属为：东南大学知识科学与工程实验室（kselab@seu ）。其实这个系列笔记实在是因为自己太笨，没法了解很多东西，觉得有必要写下来梳理一下。所以不管大家看着有帮助也好，嗤之以鼻也好，实在是没有必要转载。虽然文拙笔劣，不过毕竟也是大冬天花时间一个个字敲下来的，所以如果非要转载，我也希望注明出处。如能致此，感戴莫名！
2.1. 补充
文蛤时期，伟大的先辈发明出了一种优雅活泼奔放的喷人方法：文字皮逗。大家伙儿看谁比自己牛逼，就买横幅写大字，然后各种喷。 这个工具沿用到今天就演变成了论坛里时常聚众发生的口水战，看到别人在装，就会实在看不下去。“装”是该骂，我也看不下去！所以我要说的是，我的系列笔记绝对没有“装”的嫌疑！
上一篇笔记中，我们不断地将关注的范围缩小，最后我们集中在这样一些“计算问题”上：
①首先这个问题得有解。关于“猪睡觉会不会做梦”这个问题，好像在瑞典哪个大学有个研究小组已经取得了一些进展，而且准备冲击逗比诺贝尔奖。所以这个问题可能有解。对于一个有解的问题，问题本身和解构成了二元关系，所以我们可以用一个二元关系来描述一个问题：R= {<x1, y1>, <x2, y2>,…,<xn, yn>}，每一个二元对的左部是这个问题的输入，右部是这个输入对应的输出。
②这个问题是一个多项式平衡（polynomialbounded）的问题。即是说，问题的输出规模是输入规模的多项式级别。关于什么是“规模”？既然主要是计算机领域在考察P=？NP这个问题，我们就假设是用计算机去解决计算问题，而计算机最后都会将问题编码成二进制形式。所以，我们约定一下，这里的规模指的就是编码后，输入和输出的二进制串的长度。但是，这个约定可能让搞量子计算机，光子计算机，还有其它什么子计算机的人不爽了。这个，只能拜托这些人迁就一下了，我们这里很俗，只能用用电子计算机。
③这个问题应该对任意输入都“鲁棒”。注意，这里的“鲁”没有加提手旁，所以它是一个形容词，不是动词。特别地，对于判定问题，它的特征函数应该是全函数。通俗一点来讲，给一个任意的输入，这个问题都能进行处理。这里其实有点模棱两可，我们在谈论一个判定问题的时候，其实应该允许它的特征函数不是全函数：比如“x是不是质数？”这个判定问题。如果我们将考察的域扩大到实数范围，很显然，特征函数Prime(x)在无理数上是没有定义的，所以你得事先判断x是不是一个合法的输入，以达到“鲁棒”性。实际上，“鲁棒”是因为我们将特征函数Prime(x)和另一个函数x?N （N是大于0的自然数）进行了复合，然后得到了一个新的特征函数，这个特征函数是一个条件式，如下：
这个新的特征函数f(x)是一个实数域上的全函数——在实数这个域上都有定义。所以确切滴说，我们并不是只关注特征函数是全函数的判定问题，我们关注的判定问题是都可以改造成一个特征函数为全函数的问题。所以，约定后面所遇到的问题（包括搜索问题）对于任何输入都是有定义的。
将关注范围限定好以后，我们又在上面定义了四个问题类：PF，PC，P，NP。下面，我们试图通过简单的叙述性语言来描述这四个类（这个做法其实很危险，因为说不好就错了），首先声明，下面所谈到的所有多项式，都是针对输入规模的多项式：
? PF（polynomialfinding），给定一个输入，多项式时间内可以找到一个解的搜索问题。这里找到一个解就可以。要明确的是，不是找最优解，比如：“怎么提高大学的研究水平？”这个问题，它有很多解。当然，在这个体制里的人可以慷慨地说上一堆，但确实是存在一个最优解，小生不才，不小心发现了这个解，没错儿！“让学生被《劳动法》保护起来！”一般地，找最优解可能相当复杂，这里是找到一个解就可以，很多情况下，你也够用了。比如，刚才这个问题，有一个解是“将博士生的补贴从每月1300元提高到1500元”，我大概了解了一下，似乎国内很多理工类大学都认为这个解已经完全够用了。不扯淡了，继续。
? PC（polynomialcheckable），首先这是一个搜索问题，给定一个输入，你不一定能在多项式时间内找到一个解，但是如果给你一个解答，你可以在多项式时间内验证这个解答是不是这个输入的正确解答。有点绕，但是soeasy的，就不展开讨论了。
? P（polynomial），针对判定问题，给定一个输入，能在多项式时间内找到答案（是（true）或否（false））。实际上，对于判定问题，其定义域可以分为两类，类1对应的输出为“是”，类2对应的输出为“否”。所以P问题也可以看成“能在多项式时间内判定一个输入在前述哪类集合里”的判定问题。进一步地，这也是1.4讲的为什么一个判定问题可以仅仅用一个集合来描述，因为单用类1或者类2可以等价地把这个判定问题描述清楚了，而一般地，我们都用类1来描述判定问题。
? NP（nondeterministicpolynomial），它针对判定问题而言，给一个输入，我不一定能在多项式时间内找到答案是“是”还是“否”，但是你给我一个线索，我就可以在多项式时间内判断出来。这个比较难理解，笔记1里说NP问题是“判断某个PC问题是否有解”的判定问题。其实这样说还是不容易理解。我们重新贴上NP的定义：
定义6（NP：nondeterministic polynomial）一个判定问题S是NP问题，当且仅当，存在一个PC类问题R，使得S = dom(R)。
这个定义比通过线索来定义还要精辟。
所以，这里的关键是，那个“线索”是啥？回到PC问题，对于一个PC问题，给一个解答，可以在多项式时间内验证这个解答是不是对应输入的解答。没错儿，对于PC问题，这个事先给的解答就是“线索”。如果我们把NP问题对应到一个PC问题，那么我们就可以给些线索来多项式时间内解决问题了。
说的什么玩意儿啊，上栗子！
问题4：判断x是不是质数？
这是一个判定问题。判断质数其实是多项式时间内可以解决的（人们研究了好长时间，02年被三个阿三证明出可以在多项式时间内判定质数 [1]），所以问题4其实是P问题。那它是不是一个NP问题呢。我们要找线索，那么我们先找一个PC问题，定义6里说“存在一个PC问题”，所以我们找到一个就行。我找到下面这个PC问题：
问题5： 求x的不是1和它本身的因子？
问题5是一个搜索问题，它也是PC类问题，任意给一个数，可以在多项式时间内判断是不是它的“不是1和它本身”的因子。我们先把这个问题形式化，就是找一个二元关系R4，因为0和1是特殊情况，为了方便叙述，我们把它们排除在考察的域之外，所以R4={<4,2>,<6,2>,<6,3>,…}，但是质数本身也是合法输入，只是它们对应的输出为空。给定一个输入，我们给一个线索：一个x的不是1和它本身的因子y，我们可以在多项式时间内判断<x,y>在不在R4中。回到问题4，我们把那个因子作为线索，那当然可以在多项式时间内解决问题4。所以问题4肯定也是一个NP问题。这里的线索，学名叫证书或者证据（proof），很多定义都是基于给定的一个证书。
给了这四类问题之后，我们又接着证明了P?NP。有了上面的理解，P?NP的证明过程直观上来讲：对于P问题，本身已经可以在多项式时间内解决了，所以你给任何线索都无关紧要，所以它当然也是NP问题。
反过来，“NP是不是包含于P”这个问题，问的其实是“是不是存在一些集合，我不能很快（多项式时间内）判断某个元素是不是在这个集合，但是如果你给我一个线索，我可以很快（多项式时间内）作出判断”，这件事儿不好办，要是你看了我的笔记证明出来了，别忘了挂我的名字。（我是认真的！）
2.2. 选择
看到2.1，如果你仅仅是想了解一下什么是P=?NP问题，那么你可以不用再继续看下去了。下面就是好事者怎么去玩儿的领域了，你要是继续往下看就说明你真的感兴趣，并且有成为好事者的资质！那么是继续还是结束，现在由你选择。
2.3. 继续
嗯，我们继续吧。其实多了解一点东西没有坏处，当然我是那种懒得去学新东西的人。不过，能掌握很多东西，对一个人装B是大有好处的，这个大家可以瞄一眼知乎就能深刻地认识这个道理了。拿我举例子吧，我经常用我的Mac上装的Win7开发Android啥的（突然感觉自己在三个公司之间游刃有余），嗯，就这点伎俩，所以不必仰视我。
2.4. 等价
之前我们说，人们看待一个“计算问题”更符合情理的是将它看成一个“搜索问题”——即，搜索问题的解。也由之，红书定义了两个计算复杂类：PF和PC类问题。然后在之上给出了P和NP问题。接着，我们证明了P?NP，P=?NP这个问题也变成了NP??P这个问题。如果回到我们直观上的搜索问题，NP??P是不是在问PC??PF呢？也就是说，给一个线索，我可以很快（多项式时间内）验证是不是输入的解，那么我是不是也能很快求得这个输入的一个解呢？
下面的证明就要说明NP??P和PC??PF是等价的。一旦证明了这两者是等价的，我们就可以仅仅将注意力放在判定问题上了，也就是，我们只用去关注P和NP问题了。当然下面的证明，你若是不想看，可以直接跳到2.5节，你要是感兴趣可以?一眼。
定理2， NP?P 当前仅当 PC?PF。
证明，
先证：PC?PF ? NP ?P。假设有这么一个NP问题S，那么按照NP问题的定义，存在一个PC问题R，并且S=dom(R)。因为按照前提假设“PC?PF”，对于任意的输入x?dom(R)，存在一个算法A，能在多项式时间内找出x的一个解，或者如果x没有解，A(x)=?。在A的基础上，我们构造一个算法A’，令：
利用A’，我们可以在多项式时间内判断x在不在S中，因而S?P，进一步地有NP?P。
下面证明： NP ?P ? PC?PF。设有这么一个PC问题R，PC问题说的是，给一个输入输出对(x,y),我可以在多项式时间内判断(x,y)是否在R中（或者，多项式时间内判断y是不是x的一个解）。根据R，我们构造一个NP问题S，由定义6，这个NP问题可以是S=dom(R)。而由假设条件“NP ?P”，我们有，存在一个算法A，给定任意一个输入x，可以在多项式时间内判断x是否在S中。那么问题来了，我们能够否在A的基础上构造一个算法A’,使得可以在多项式时间内找到x的一个解。
按照定义6，这个事儿不好办。实际上定义6反过来也说得是“一个搜索问题R是PC问题，当且仅当，存在一个NP类问题S，使得给一个输入x?S和一个线索y，可以在多项式时间内判断(x,y)?R。”所以，我们可以任意构造一个对应的NP问题，我们不采用定义6的构造方式，我们构造一个新的NP问题：S’={xy’|x?dom(R)??y”,s.t.(x, y’y”)?R}，意思说的是，我们将R的一个任意输入x，和它对应的一个解y的任意前缀组成的串（这里假设已经编码成了01串）作为S’的元素。由于这些问题都是多项式平衡的，这里S’的规模肯定是S的多项式级别，即：|S’|<=p(|S|)。由假设条件“NP ?P”，我们有，存在一个算法A，给定任意一个输入x，可以在多项式时间内判断x是否在S’中。现在，我们可以根据算法A构造这么这个算法A’来找到x的一个解：
while循环其实是遍历所有可能的01串，看看哪一个是x的解。但是由于假设条件“NP ?P”，也就是任意的串xy’可以多项式时间内判断在不在S’内，如果y’后面添一个0也在S’内，那么让y’0代替y’；如果y’后面添一个1在S’内，那么让y’1代替y’。这个过程是多项式的（因为多项式平衡），因而A’算法也是多项式时间内可以停机的。因此，R?PF，也就有了PC?PF。证毕。
2.5. 同构
我相信一定不会有很多人喜欢看像2.4中这样的证明过程，不是因为大家觉得自己没有数学方面的兴趣，而是更多的人会想，有这个闲情还不如想想买什么股，研究研究K线图啥的！真正看这些证明会产生多巴胺的，在我们“普通人”看来就已经是奇葩了。
所以，我有时会想，要是哪天，数学类教材上把这些证明写得很有意思，那该多好，至少我们这些凡人会觉得数学家还是体恤民心的嘛。这里的有意思不是让数学家感到快感的那种“有意思”，而真的是“有意思”的那种有意思。也许你会说，很多教材都做到了啊，把一个深奥晦涩的证明用普通人看得懂的方式讲明白了啊。其实这些教材做的是这样的事：首先你已经知道我们要证明什么了吧，比如2.4中要证明NP??P和PC??PF是等价的，OK，那这个普通人看得懂的方式其实是在说“你就甭管细节了，你也看不懂，不管怎样我是帮你证明出来了，你看你已经懂了结论，不是挺好的嘛。”
不过毕竟，有些好事者并不接受上述这种“普通人看得懂的方式”，他们想了解到底这个结论是怎么来的。任何通过作者理解归纳过后的叙述都会让他们不满足，因为毕竟不是自己理解得出来的。这样一来，又要陷入得把详细证明列出来而让其他人不爽的尴尬境地。要解决这个问题，只有一个方法：同构！
就像爱因斯坦给小伙子解释相对论，我们也找一个所要证明的问题（比如NP??P和PC??PF是等价的）的同构的问题，这个同构的问题要“够俗，够萌，够贱”。然后证明这个“三够”问题。这样既给出了详细过程，又使得“普通人都看得懂”，岂不是一举两得！
同构是一个伟大的思想，这个思想属于自然界，是不以人的意志为转移的。W老师课上推荐了一本书：《GEB》，中文名《集异壁之大成》。书的作者是搞逻辑的，某天发现哥德尔的数理逻辑、艾舍尔的绘画还有巴赫的音乐竟然是那样地相像，这个“像”就是他们在很多方面竟然都是同构的。于是，作者脑洞大开，洋洋洒洒挥墨千页，分娩出了这部神一般存在的书。
大家感兴趣可以把这本书找过来拜一拜。那么接下来，我也试着去找定理2的同构问题。思来想去，找到了一个“特俗，特贱，特没节操”的“三特”问题。既然定理2涉及到了四个对象：PC，PF，NP以及P。那么我们首先把这四个对象同构到这个三特问题的四个对象上。先声明，因为目前天朝社会基本上是一个看脸的社会，所以为了让大部分人看得懂，找到了下面这个三特问题，另外，请大家不要对号入座！
PF：对应到这个问题：长得漂亮的人会发生什么？一般而言，长得漂亮的人会发生什么事情都比较“简单易懂”，所以可以在“很短的时间段内”找到一个解，比如“长得漂亮的人比较受校长的青睐”等等之类的。
PC： 对应到这个问题： 形象好的人会发生什么？形象好的人，我们从内心里尊敬他们，但是一定要说他们因为形象好会发什么，我们不一定很快找到一个答案。但是你给我一个线索，比如“食堂打饭时大妈特别热情地多盛了一块肉”，那我可以判断一定是因为这家伙已经坚持刷牙一个礼拜了。然后暗暗地痛下决心，从明天开始也坚持刷牙！
P：对应到这个问题：长得漂亮的人。我们知道判定问题可以用一个集合来描述，这里也用一类特定的集合来描述。这个问题详细点就是在问“x长得漂不漂亮？”
NP：对应到这个问题：形象好的人。同样，这个问题有一个对应的PC问题，给一个线索，我可以验证某个人是不是形象好的人。
现在我们已经证明了P?NP，对应到上面就是“漂亮的人形象都很好”。也许具有人文关怀的你要喷我了，说我“三特”，但请相信我，很多人觉得漂亮的人形象好并不是根据他们的穿着打扮是否得体，而是根据自己肾上腺素的分泌量。
进一步地，定理2翻译过来就是“一件因为你形象好而发生的事情一定也是因为你漂亮”和“形象好就是漂亮”是等价的。说一件发生在我身上的事情。我们家楼下住着一个女神。大四的时候，因为要经常出去面试笔试，所以回到家也习惯穿着西装（因为经常一段时间，我都懒得换衣服）。每天出去前，都是西装革履，梳妆打扮一番。某天在电梯里遇见女神，自己已经不能呼吸了，然后她的东西掉落的一刹那，我以迅雷不及掩耳盗铃之势接住后还给了她，她愣了一下，向我莞尔一笑，说了声“谢谢。”那个时候，我无比相信，这就是缘分，这是上天安排的，没办法，一定是因为漂亮的人之间是相互吸引的。于是接下来几天都甜蜜地失眠了。后来几次，在电梯里碰见她，她都向我点头致意，我想，恩，这份安排已经再明显不过了。可是，万万没想到！！有一天早上，我没有刷牙，没有梳头，还穿着睡衣下楼去拿牛奶，意想不到地在电梯里遇见了她，而且也意想不到地，她就像不认识我一样，对我熟视无睹，我的心在那一刻，碎了。这之后，我成熟了，长大了，然后，就没有然后了。相信我，NP肯定是不包含于P的！
大家不用为我难过，我只想让你们知道：“同构”是一个伟大的思想。而这个伟大的思想在接下来会引导我们发现另一件神奇的东西：归约。
2.6. 插话
红书中给了一段用哲学的观点来看P=?NP这个问题的叙述。这里我只是搬运而已。
说哲学家以前都坚信：如果一个系统还有在这之上的问题可以被很好地形式化地描述，那么这些问题一定可以解出来。这个想法一直到20世纪还被大家相信着，以至于希尔伯特一帮人准备搞出一个宇宙大一统的数学系统。然后，突然有一天，哥德尔把这个梦打破了。我就不介绍哥德尔不完备定理对当时的世界带来多大的风暴，要介绍的话也是贴的百度百科。举个简单的例子：
下面这句话是错的，
上面这句话是错的。
究竟这两句话谁对谁错，大家绕一绕吧。拿普通人的理解，哥德尔不完备定理其实指出了，系统中的某个错误或者不一致不一定是通过系统本身导致的（或者被系统定义出来的），而是由于更复杂、或者更无法理解的原因导致。
回到P=?NP的问题，通常人们会直观地认为，一个问题可以多项式时间验证其解答，不一定就能多项式时间求得它的解。如果把哥德尔不完备定理作为佐证，那么似乎也会存在某个NP问题，它求取解的过程可能由更复杂、或者更无法理解的因素作用着，而这些因素也使得这个过程不能在多项式时间内高效地完成。
2.7. 参考文献
[1] M. Agrawal, N. Kayal, and N.Saxena, “PRIMES is in P”, Ann. of Math. (2) 160:2 (2004), 781–793.
原文：http://my.oschina.net/airship/blog/376554