独角兽企业重金招聘Python工程师标准>>>
计算复杂性读书笔记（一）： 判定问题，P，NP 比特猪 quanzz1129@
首先是版权声明，版权归属为：东南大学知识科学与工程实验室（kselab@seu）。其实这个系列笔记实在是因为自己太笨，没法了解很多东西，觉得有必要写下来梳理一下。所以不管大家看着有帮助也好，嗤之以鼻也好，实在是没有必要转载。虽然文拙笔劣，不过毕竟也是大冬天花时间一个个字敲下来的，所以如果非要转载，我也希望注明出处。如能致此，感戴莫名！
1.1.好事者心态
关于该系列笔记的内容：仅仅谈谈P=?NP的问题的由来始末，包括什么是P、NP问题，什么是P=?NP问题，以及NP完全性理论的相关证明。阅读这个系列笔记需要一点离散数学的背景知识。参考书是以色列科学家Oded Goldreich的《ComputationalComplexity : A Conceptual Perspective》（因为人民邮电出版社的影印版是红色的，我们后面就叫它红书吧）。这家伙原来是搞密码学、随机性的，所以这本书也夹了很多私货。不过W老师竭力推荐。读过书之后，觉得W老师的推荐确也是有理由。
我一直认为自己只是个计算机好事者，谈不上涉猎，更谈不上精通。而这本书实在是适合一个好事者去读的。说实话，当你认为自己只是个好事者的时候，你对一样东西的接受力是最高的，你此时的心态是最开放的。但当你认为自己在这个领域有所建树了，开始区分优劣了，其实也意味着你可能开始固步自封了。看了铃木俊隆的《禅者的初心》一书后更加体会到了这个道理，所以“好事者”一直是我给自己贴上的自我标签！
不久前看了王垠的《谈“P=NP?”》。这个人是神一般的存在，大家伙儿可以自行百度，而且绝对是个大喷子。同样，在那篇文章中把P=?NP这个问题还有为这个问题殚精竭虑的所有科学家们喷了一遍。不过，喷的理由和很多反对者意见一样：仅仅用多项式问题来囊括一类问题太过宽泛。从实际的角度来讲，2^n时间复杂度的算法绝壁要比n^1000000好太多，所以谈论P=?NP本身没有意义。仔细想想，这样的理由不是没有道理，但是它不能否认P=?NP问题的存在。既然这个问题存在，就必然有“好事者”去管这个闲事。在科学家当中，研究型偏执症候群是很普遍的，通俗来讲，这个问题“有意义还是没意义”对他们来说就是没意义的，只要好玩儿就行，咱就想把它搞搞明白，至于它能否给你们生产上的指导、是否能推动经济发展，通通都不（guan）予（wo）考（pi）虑（shi）。
不管怎样，我是以“好事者”心态来了解这个问题，所以本质上也是“好玩就行”。不过，看了一眼Oded的书之后，心里顿时陷入极度恐慌。我发现很多概念都被以往的各种老师“坑”了，比如曾几何时某位老师在讲“什么是P问题”的时候，为了方便，就直接跟我们说：“P问题就是多项式时间可解决的问题。”你好歹先说清楚是相对于什么而言的多项式时间吧，所以以至于一段时间我以为有一种时间叫多项式时间。这不算什么，我恐慌的是，不知道还有多少概念以为是那样，但实际上是被“坑”了。不过，这不怪老师，只能怪我太相信老师。
目前来讲，这其实没有办法，现在高校的大部分老师都忙着赚钱，至于P=?NP这类问题真的是不（guan）予（wo）考（pi）虑（shi）。前不久听了一个Z大学来的教授的讲座，这个教授说在Z大学，哪个老师不开个公司呢，你如果不开都不好意义混了。所以，我想，哦，其实Z大学的老师们都忙着IPO呢。相信我，还有一大部分老师兢兢业业，是真正喜欢做学术的，我身边就有好多这样的例子，比如我的导师，还是W老师。只是天朝环境所迫，没有办法。好了，停住！这个问题就不谈了，它绝对是多项式时间谈不完的。回到P=?NP问题，我们还是把自己仅仅当成好事者吧，没有任何心理负担，用最open的心态去了解了解它。
1.2.描述一个计算问题
既然我们要谈计算复杂性，那么首先来谈谈什么是“计算”，更确切地说：什么是一个计算问题？当然很多人会说：我们生活当中的计算问题几乎无处不在，然后脑洞大开地巴拉巴拉说了一堆。我们这里的话就不谈了，大家自行脑补。我们谈谈怎么去描述一个计算问题，以此切入。
对于一个计算问题来讲，你得首先有一个问题，然后这个问题得有解答（当然，可能有多个解答），没有解答的问题，比如：猪睡觉时会不会做梦？嗯，这类问题我们就不关注了，既然连解答都没有，就更谈不上计算它的复杂程度。所以我们谈的问题，首先都是有解的。为了研究计算一个有解问题的复杂程度，我们得首先将什么是一个“计算问题”进行形式化描述。形式化描述能说清楚很多事儿，有些教科书会直接“啪啪啪”地上几段自以为很高明的论述来说明一些概念，然后引发你的无限联想，对于这类教科书的具体功用，我建议你这月不要专门买厕纸了。
一个问题，从程序猿的角度来看，就是一个输入；这个问题的解答就是输出。问题（输入）和解答（输出）构成了一组二元对。所以直观地，我们可以用一个函数去描述一个计算问题，函数的定义域和值域自然地构成了一组二元对，定义域为问题的输入，值域为问题的输出。由于输出可能有多个，所以更确切地说应该是一个映射。因而，更自然地一种方式是用二元关系来描述一个计算问题，这个二元关系是二元对的集合，每一个二元对的左部作为这个问题的输入，右部作为这个问题的输出。
快晕了，直接上例子。下面的例子是W老师给我们的课堂练习，其实是他四年级女儿的数学竞赛试卷的第一题：
问题1： 求能被11整除的五位数的回文数。
当时我们就集体醉了。而且由于竞赛过程中习题的密集性，像此类问题要求在两到三分钟之内解答出来。我只想说：尼玛，太凶残了！
还是回到我们的话题上来，对于问题1，我们抽象一下：求能被n整除的五位数的回文数，这里的n是一个大于0的自然数。那么问题的输入就是11，输出是对应的可被其整除的回文数：11511，22222，10001 ……。因此问题1有一个对应的关系，比如叫R1，那么R1定义为：R1={<11,11511>, <11, 22222>, <11, 10001> , … … }这样的二元对的集合，每一个二元对的左部是输入11，右部是所有满足条件的五位回文数。
在后面的叙述中我们就采用二元关系来描述一个计算问题。
1.3.多项式平衡（polynomial bounded）
很多计算问题，它的输出规模比输入规模大得多。比如：求解11以内（包括11）自然数的全排列。这个问题输入仍然是11，但是输出不单单是某一个排列，而应该是所有的排列。如果用长度（比如，11的长度就是两个数位）代表规模，那么这里的输出长度会是输入的指数级。对于这一类问题，我们也不考虑，我们认为这一类问题天然地是极其复杂的问题，或者有的人称之为“顽型问题”。我们集中在处理“输出规模是输出规模的多项式级别”这一类问题上。好吧，也许你要说，既然把这些难的问题都抛弃了，那还研究个脑袋啊。确实，我们仅仅集中在“稍微复杂，但又不太复杂“的这一类问题上。依W老师的说法，其实这一类问题已经涵盖了我们生活的绝大多数问题了。
定义1：一个问题R，存在一个多项式p，对于所有的二元组(x,y)∊R，如果|y|<=p(|x|)，那么R是一个多项式平衡的问题。
1.4.判定问题（Decision problem）
1.1中的那位介绍P问题的老师其实说的没错，完善一下就是：P问题是关于输入规模在多项式时间内可解决的一类问题。这个其实是符合我们生活常识的，对于一个问题，我们要做的就是“寻找”这个问题的解（当然，解可能不唯一）。所以其实可以把所有计算问题都看成是“搜索问题”——即，搜索这个问题的答案。不过，从P=?NP问题被研究以来，几乎所有的人都用“判定性问题”来定义P和NP类问题。至于为什么？没错，就是为了省事儿。以至于越到后来，人们越发地认为判定性问题其实是所有计算问题的变式或者本质，即是说，所有计算问题都可以规约到相应的一个判定性问题。
那么，什么是一个判定问题？很多地方都简单地说：判定问题就是答案为1（true）或者0（false）的一类问题。这种说法其实不太严格。
我们还是以例子说明：
问题2： 求100以内的质数。
100是问题的限定范围，这个问题的实际输入应该是一个100以内的自然数，输出是“是（1）”或者“否（0）”。设这个问题对应的关系叫R2，那么R2={<2,1>, <3,1>, <4,0>, <5,1>, …,<100,0>，<101, 0>,<102, 0>, …}，注意大于100的质数，其对应的输出也为0。
R2的输出既然仅仅为0或者1，我们可以直接用R2中二元对右部为1时所对应的左部的集合来描述这个问题，或者不严格地说，用R2的定义域来描述这个问题，比如R2’：R2’={2,3,5, … , 97}。为了描述方便，我们引入一个谓词Prime(X)，如果X是质数，那么Prime(X)= 1，否则Prime(X)= 0。由此，R2’可以写成下面的形式：
R2’={X|Prime(X)= 1⋀X <=100}
R2’这个集合其实已经清楚地描述了问题2，你可能不太能理解，但确实是这样。简单解释一下，R2的定义域是自然数，R2’是R2定义域的一个子集，这个子集中所有的输入其对应的输出都为1；那么R2定义域中不在R2’中的输入其对应的输出都为0。所以R2’和R2是等价的。你也许会问，是不是也可以用二元对右部为0时所对应的左部的集合来描述这个问题，比如R2”={X | Prime(X) = 0⋁(Prime(X)= 1⋀X <= 100)}。当然这是可以，不过R2’更直观些，至少对于问题2，R2’同时给出了所有答案。
在红书中，对于判定问题是如下定义的：
定义2：一个判定问题R，存在一个特征函数f : {0, 1}* -> {0, 1}，使得对于任意的x，如果f(x) = 1当且仅当x∊R。
上述定义中f的定义域为{0,1}*，这里假设对问题进行了二进制编码，问题的输入就是0和1的组合串。回过头来看R2’，它的特征函数就是f(x)= (Prime(X) = 1)⋀(X <= 100)，这个特征函数本身是一个布尔函数。
如果仅仅从这个定义来看，对于x不在R中情况，定义本身并没有限定f(x)一定取值为0。有可能f在某个x的上无定义，换句话说x不在f的定义域中。此时f的输出既不是1也不是0。因此，简单地将判定问题说成是输出0或1的问题不太严格，因为有可能没有定义。在可计算性理论当中，这样的集合称为递归可枚举集（recursive enumerable set），集合中是该问题有定义的输入集合。它的特征函数可能在某些取值上没有定义，这样的函数也成为部分函数（partialfunction），如果在所有取值上都有定义，便称为全函数（totalfunction）。
所以，判定问题（现在我们已经用一个集合来表示一个判定问题了）的特征函数有可能是部分函数。如果给一个没定义的输入，那么计算机就逗比了，给不出一个答案，因此可能永远无法停机。如果遇到这种情况，那么这个问题就是不可判定的。
但是通常，我们所遇到的问题，在程序实现的过程中我们都能找到条件判断一个输入是不是合法输入（或者叫异常处理更合适），这种情况下，这个问题（假设是判定问题）的特征函数就是全函数。
提出判定问题，是为了定义P和NP类问题。所以这里，我们再限定一点，我们考虑那些特征函数为全函数的判定问题。
1.5.抛开图灵机
1.2到1.4我们不断地在缩小我们关注的范围。到这里，我们可以开始给一些复杂性问题类了。在给出定以前，我们先抛弃一样东西：图灵机。
不管是红书的作者还是W老师都坚持抛弃它。W老师义愤填膺地说：“几乎所有的书都沿用最初的基于图灵机的定义，都没点儿自己的想法，你抄我，我抄你。”于是Oded有想法了，抛开图灵机，探究问题的本质。确实，加上图灵机，会显得很别扭。P和NP问题是一类很自然的不以人的意义为转移的朴素存在的问题（怎么有点像政治书上的说法，汗一个），偏偏要加上图灵机来定义，太别扭！而且也如王垠所喷，非确定性图灵机从来都没造出来过，仅仅是人们脑补出来的东西。所以，我们紧跟时代的步伐吧，抛开图灵机！
1.6. PF和PC问题
红书中花了大量篇幅谈“用判定问题来定义P和NP问题并不直观”。人们对于一个问题更常规的看法应该是如1.4中一开始所谈的“搜索类问题”。用判定问题来定义是为了省事儿，不过所有搜索类问题都有一个对应的判定问题：“对于这个搜索问题的某个输入是不是有解”。更严格说，判定问题应该包含于搜索问题，因为判定问题就是搜索范围为0或者1的搜索问题。
搜索问题是更自然的一种角度。因此，红书中给出基于搜索问题所定义的两个复杂性问题类：PF和PC问题。
定义3（PF：polynomial finding）一个搜索问题R是PF问题，那么存在一个对于输入规模是多项式时间的算法A，要么<x, A(x)>∊R,要么A(x)=∅。
定义中有一点得注意，PF问题中的搜索问题存在一个多项式时间的算法，这个算法只要求给出对应输入的一个解即可。对于绝大多数问题，给出所有解当然很好，不过给出一个解也已经够用了。
定义4（PC：polynomial checkable）一个搜索问题R是PC问题，那么存在一个对于输入规模是多项式时间的算法A，使得给定一个对<x,y>，如果<x,y>∊R，那么A(<x, y>)=1,否则A(<x, y>)=0。
直观地来看，PC类问题是这样一类搜索问题：给定一个输入和输出，可以在多项式时间内判断这个输出是不是这个输入所对应的正确输出。
已经晕的一塌糊涂了，上例子。我们回到问题2。
问题2： 求100以内的质数。
你可以跟阅卷老师说，你让我求100以内的质数，又没有让我求100以内的所有质数，所以我就写一个2也应该给全分啊。当然阅卷老师可能直接把试卷糊到你的脸上。
我们在这里会对你说，没错儿，你已经找到了一个PF问题。PF问题说可以在多项式时间内找到一个解。对于问题2，我们首先得问判断一个质数可不可以在多项式时间内完成。这个问题不那么容易，我们直接给结论，问题中限定在一个较小的范围——100以内，所以是存在一个多项式算法的（这个大家伙儿可以自行谷歌）。回到问题2：限定范围是n =100，如果用二进制编码就是logn位，即使将100以内的所有数都遍历过去，也只要O(2^logn)=O(n)的时间，更别说只找一个解就停机的情况，所以问题2肯定是属于PF类的。它同样也是PC类问题，任给一个对，比如<47,0>，只要判断47是不是质数就行了，如果是的，由于<47,0>的右部为0，那么算法输出为0。
1.7. P，NP问题
在这里，我们秉承传统，用判定问题来定义P和NP问题。
定义5（P：polynomial）一个判定问题S（注意，这里的S是一个集合）是P问题，那么存在一个对于输入规模是多项式时间的算法A，使得对于任意的x，如果A(x)=1当且仅当x∊S。
直观地来看，P问题就是一类特殊的判定问题：对于任意一个输入，都可以在多项式时间内判断这个输入的答案。如果用集合S来描述这个一个P问题，那么意思就是可以在多项式时间内判断某一个取值在不在S当中。能判断“在不在”是有前提条件的，就是1.4中所说的它的特征函数应该是全函数，对于任意的输入都可以给出一个判断。
问题2所对应的判定问题可以这样描述：100以内的自然数给我挨着盘儿地判断一下是不是质数。用集合来描述就是R2’。那么是否存在一个多项式时间的算法来判断一个任意的输入在不在R2’里呢。很显然，R2’的特征函数Prime(X) = 1⋀X <= 100就是这个算法。所以问题2所对应的判定问题也在P问题类中。
定义6（NP：nondeterministic polynomial）一个判定问题S是NP问题，当且仅当，存在一个PC类问题R，使得S = dom(R)。
这个定义很简洁，很漂亮，它甚至抛弃了证书（proof）这个概念。但是不太容易理解。仔细琢磨一下，这个定义其实把搜索类问题和判定问题联系在了一起。虽然表面上看上去是在用判定问题定义NP，但是实质上是在用一个搜索类问题定义NP。我们从“当且仅当”的右边看起：给一个PC类问题R，隐含的意思是存在一个多项式时间的算法A，使得给定一个对<x,y>，如果<x,y>∊R，那么A(<x, y>)=1,否则A(<x, y>)=0。dom(R)的定义是：dom(R)={x|∃y s.t. <x,y>∊R}，即取得R的定义域。用这个定义域来给出一个判定问题S=dom(R)，这个判定问题可以理解为：搜索问题R是否有解，其所对应的描述集合是所有有解的输入之集合。所以NP问题类直观上可以理解为“判断某个PC问题是否有解”的问题之集合。
1.8. P⊆NP
下面证明P类问题包含于NP类问题，证明本身很简单，W老师说：“大部分教科书都不会给这个结论的证明，因为弄不好会侮辱到读者的智商。”不过，我们这里简单证明一下，为的是更深入地理解NP问题。
定理1，P⊆NP。
证明P⊆NP，我们实际上是证明对于任意一个判定问题S，如果S∊P，那么S∊NP。展开定义，首先啥是P问题，就是存在一个对于输入规模是多项式时间的算法A，使得对于任意的x，如果A(x)=1当且仅当x∊S。为了证明S∊NP，我们首先得找到S所对应的某个PC问题。因为只要存在这个PC问题就行，我们就构造一个PC问题。构建一个搜索问题R，令R=S X {0, 1}*，这个问题的意思是，对于任意的输入，它的解是任意的值。通过A，我们得到另一个算法A’，使得A’(<x,y>)=A(x)。因为y是可以是任意的值，所以只要输入x在S里，那么就有<x,y>∊R，进一步就有A’(<x, y>)=1,否则如果x不在S里，此时A’(<x, y>)=0。很显然，A’也是多项式的。所以R是一个PC问题，进一步，S∊NP。证毕。
那么反过来呢？NP问题是否包含于P问题。回到1.7中，一个NP问题本质上是“判断对应的PC问题是否有解”，而PC问题只是在给定输入输出对<x,y>的情况下才能多项式时间内判断<x,y>是否属于R，任意给一个x，能不能知道x是否有解（或者是否在判定集合里）这件事儿还不确定能不能在多项式时间内完成，所以NP不一定包含于P。
P=?NP问题现在就变成NP是否包含于P的问题了。这件事儿还真不好办，以至于一个叫Clay Math的研究所悬赏100万美元给解决它的人。
