半瓶

导语

本文力求在万字篇幅内尽可能清晰地介绍计算理论的基本概念和最新发展。

普通科学读物总是逻辑清晰环环相扣，但是这实在把读者累坏了。本文作为心疼读者的二逼科学读物，目标是希望读者在看不懂第一章的情况下仍有可能把第二章看下去。对于涉及到的新兴专业术语，作者将做出尝试性的汉语翻译，用汉语的语法、汉语的风格、汉语的词汇展现全文。

可计算性问题

现实生活中有很多计算类的问题，考试要计算成绩，购物要计算价格，与佳人约会要算好时间，出门旅行要算好乘车方案。计算的结果不局限于数字，也可以是方案，可以是图像，可以是子弹穿过木块的运动轨迹，也可以是组成新款计算机的电路设计。只要一份答案可以用语言描述，它就可能是某个计算过程的结果。

可是世界上并不是所有问题都能算出结果。姑娘的头发有多少根，这个问题很难，但是交给机器做，一根一根数，数一根拔一根，总是能数完的。这个问题就可计算。但是姑娘明天心情如何，这个问题就根本没办法计算了。事实上就连她们自己也弄不清楚。

那么，什么问题是可计算的？什么问题是不可计算的？我们能不能在数学上给“可计算”下一个精确定义，然后用数学手段研究万事万物的可计算性？

历史

这个问题的源头早在17世纪就被提出来了。欧洲大陆近现代数学的共同导师莱布尼茨，在发明了相当完善的微积分体系后，马不停蹄地试图再发明出一套数学机制来判断任何逻辑陈述的真假。但是这个问题的难度已经远远超出了莱布尼茨的时代，首先，莱布尼茨缺乏数学工具去描述逻辑陈述本身；其次，也没有成熟的逻辑知识去帮助他理解逻辑。但是他已经隐隐地感受到，有必要创造出一种“形式语言”来描述问题。

世界上最后一个通晓所有数学领域的数学家希尔伯特，用他的天才智慧和完美主义创造了完善的希尔伯特公理体系，构建了完整的逻辑规则，在一阶逻辑上找到了既可靠又完备的演绎系统。1928年，在逻辑学基础上，他正式提出了这个问题，数学史上大名鼎鼎的判定问题，德语Entscheidungsproblem，英语Decision Problem：我们能不能找到一种算法来判定一切一阶逻辑陈述的真假？

“算法”“一阶逻辑”这样的字眼实在晦涩费解，事实上算法我们就可以理解为一种可行的方法或机制，而一阶逻辑是数学中公理系统的标准形式逻辑，大部分判断句都可以用一阶逻辑的陈述来表达。而那种经常会产生悖论的“整数和偶数一样多”这类蕴含着“无穷大”概念的判断，则不在一阶逻辑范畴之内。这些给数学和逻辑添麻烦的魂淡问题，我们今天就先不理会了。

所以我们可以用更形象的语言来描述这个问题，这个问题是在问我们，我们能不能造出来一个黑箱子，做对这世上一切判断题？

咦？这个问题看起来强度有点弱啊，我们刚才是可以数女生头发数目的，我们是可以做解答题计算题的，可是这个判定问题只对判断题有要求。

没关系，很多计算题也可以转化成判断题。我们只要不断地向黑箱子问：“她有1根头发吗？”“她有2根头发吗？”……只要你寿命够长能把问题问完，总有一天，你会得到正确答案。一上来就直接考虑计算题，对我们而言太难了，所以我们先从判断题开始吧。

形式语言与图灵机

语言

莱布尼茨需要一种工具来描述问题。描述问题，当然需要语言。什么语言呢？中文？Engish？二进制数码1111111111？printf(“C++”)？吙煋呅？都不是。下面我要隆重推出高端大气上档次的形式语言，一大波定义即将袭来，大家耐耐性子，文科生也能看懂的~

直观上说，语言都是字符串组成的，这里的语言也不例外。我们假设字母表Σ为任意有限集合，表示空串，记为，。

定义：语言为的任意子集。

举个例子，假设字母表 = ，那么，把所有的并起来，就得到。这样所有有限长的SB串就都包括在\(\Sigma^\)里了。我们取\(\Sigma^\)的任何一个子集，就都构成一个语言。

全串，全串，只有一个的串，和一样多的串，……他们都是字母表上的语言。给定任何一个字母表上的字符串，给定一个上的语言，判断是否属于，也就等价于做一道判断题。

图灵机

阿兰·图灵，英国杰出的同性恋数学家，二战时德军密码的破译者，计算机科学的宗师，在1936年5月发表了一篇划时代的论文《论可计算数及其在判定问题中的应用》。判定问题就是我们上文提到的希尔伯特判定问题；可计算数，就是我们上文提到的可以计算出来的答案。图灵为了解决这个问题，发明出了一台惊世骇俗的机器模型，说只要是这台机器能计算的，就是可计算的；这台机器能判定的，就是可判定的。此机一出，判定问题彻底终结，江湖人称“图灵机”。

说到这图灵机啊，结构十分简单。一条长长的纸带，一个读写头，读写头指向纸带上的一个格子，可以在纸带上自由地左右移动，这就没了，和我们这一代人小时候常见的磁带机差不多。当然了，也有区别。纸带是无限长，划分成无限多个格子，每个格子里可以填一个字符。这里也可以填，也就是啥也不写，空在那。读写头有个状态，初始时，读写头的状态是，位于纸带上某个字符之上，读写头会根据和这两条信息，决定做出三件事：

1. 把x改写成字符y
2. 向左或者右移动一格
3. 把自己的状态切换为某个

这种决定不是读写头一拍脑袋想的，而是我们事先设计好的。我们事先就决定好了一台图灵机的字母表、状态集、 读写头在每个的情况下做出什么动作，机器在达到哪些状态的时候停下。

好了，一台图灵机的结构就这么简单。让我们来看几个例子吧。

识别与判定

我们假设图灵机有两个停止状态，当读写头切换到这些状态的时候，图灵机就停止了。如果图灵机停在，我们称它接受（accept）了输入串；如果停在，我们称它拒绝（reject）了输入串。

定义：如果存在一台图灵机可以接受语言中的所有串，我们称是可识别的。

定义：如果存在一台图灵机可以接受中的所有串并拒绝中的所有串，我们称是可判定的。

我们现在把都设置成，也就是二进制码。设为所有全0串的集合，那么我们很容易发现是可判定的。

证明：构造一个图灵机，它有3个状态, , 。再设置读写头的工作函数，使得。这个图灵机就可以判定。

这个例子太简单，大家可以试试看怎么构造图灵机判定所有回文串的集合。

此外，这个世界上还有很多奇葩问题——或者说语言——是只能识别不能判定的。比如说大名鼎鼎地停机问题：给定一台图灵机和一个输入串，让图灵机能在这个输入串上运行，请问这台图灵机能停下吗？

我们可以很容易地识别出能停下的情况，只要模拟这台图灵机的运行情况就可以了，一旦停下就对外声称这个图灵机可以在这个输入下停止；但是如果不停呢？对不起，数学家已经证明，没法识别。

理论、算法、应用

我们现在手头已经有了语言和图灵机这两大工具，已经可以开始建设计算机科学的理论大厦了。在这之前，我认为非常有必要提一提理论的意义。

昨天小师妹段萌软就问，理论是神马？理论可以吃吗？

很遗憾，大部分第一流的理论研究不仅不能吃，甚至都是没有“用”的。它离我们的现实生活实在太遥远，写不出百度也造不出 QQ，不能让我们的选课快上一秒，也不会让情侣间少丢几条短信情话。

理论研究的问题往往是，“如果明天的天气可以预测，那么女孩儿的心情也可以预测”这种命题？这个问题如果证明了，就是理论界的重大突破，我们只要能预测天气，就能猜对女孩儿心思了。多么美妙啊！可是，现实中大家既不能预测天气也不能预测女孩儿的心思，所以这个命题不管被证明还是被推翻，对于我们的现实生活一点帮助都没有。大家和妹子交往，还是要看天吃饭。

哎，我把理论说得也太不堪。事实上理论不仅对于现实有深远指导价值，其本身蕴含的智慧更是人类精神文明的伟大见证。

计算机科学的宏伟格局，理论、算法、应用，三位一体，缺一不可。

譬如我们想为广大懒助教提供一个自动批改试卷选择题的程序，这一程序就是应用。为了做出这个应用，我们需要设计一个识别正确答案的算法，而理论告诉我们这个问题是可判定的，我们一定能找出一个算法解决问题。

应用有时会驱动理论的发展，譬如，如果助教希望这个程序还能够批阅解答题，那么我们就需要为解答题设计新的算法，这可太难了，我们的程序得能理解语义才行。能否让程序去理解自然语言的语义，这就是一个理论问题了。只有理论解决，我们才能够提出切实可行的算法，来实现这一应用。

相反，理论的进步也可以指导应用的发展。比如，理论告诉我们，一个问题是不可解的，那我们设计算法时就可以避开这个地雷。又如，理论告诉我们，在二维平面上随机游走会无限次经过原点，那么我们在设计算法的时候，就可以设计回到原点后程序的种种行为，不用担心无法返回。

诚然，理论是一切方法和应用的基石，就像物理理论是电灯、电脑、汽车、楼房的基石一样。没有理论支持，我们也可能造出电灯泡。但有了理论支持，我们就能知道电灯的原理，就可以研发各种新款电灯。另一方面，理论还能证明使用电灯既不会导致核爆也不会导致怀孕，这样大家用起来才安心，才能确保在重要场合使用电灯不会带来一些难以预料的副作用。

然而，大部分理论就像我前文所说，是基本上没用的。理论就像法拉第口中的婴儿，只有长大了才能彰显出独特的价值。

计算的时间复杂度

P vs NP

任何计算过程都需要耗费时间与空间。对于图灵机而言，读写头移动的次数就是消耗的时间，读写头走过的纸带格子数就是占用的空间。如果输入串的长度为，图灵机的时间消耗不大于，我们称这个语言可以在时间内得到判定。如果是关于的线性函数，我们称该语言可以在线性时间内得到判定；如果是关于的多项式函数，我们称该语言可以在多项式时间内得到判定；如果是关于的指数函数，我们称……后面就不用我多说了吧。

对于那些可以在多项式时间内得到判定的语言，他们组成的集合就是，单词多项式polynomial的首字母，大名鼎鼎的。

是语言的集合，这些语言的判定问题我们俗称问题。

至于那些可以在多项式时间内得到验证的语言，它们的集合就叫做。

什么叫验证？什么叫？直接说太麻烦，让我们看个例子吧。

问题：OrangeCLK 期末论文写不完了，想找人代写。可是这事儿可绝对不能让老师知道，所以一定要找他的死党。OrangeCLK 是个 geek，他居然用数字来表示他和朋友间的好感度。他说了，只有好感度超过 100 的朋友才算死党，现在给你一份包含陈力坤所有朋友好感度信息的数据表格，问他能找到个朋友帮他代写论文吗？

这是一道不折不扣的判断题，而且它在多项式时间内就能做完，图灵机只要一一扫过那些数据，数数有没有个大于 100 的数据就可以了。图灵机可以很聪明地数数，它现在纸带某个空白的地方写上，并且每扫描一个数据就擦除掉，每发现一个满足要求的数据就跑到写的地方给减一。如果能减到 0，图灵机停止运行，OrangeCLK 论文得救，如果图灵机看遍所有数据，原先写的地方还是个正数，那 OrangeCLK 就只能挂科了。好，这里给读者留个题目，图灵机怎么做加减法呢？大家有兴趣就自己动手设计个函数试试吧。

我们看到，给定输入，存在一台图灵机先验证是不是这样的格式，然后执行上述算法，就可以在关于的多项式时间内判断问题的是或否。所以 属于 P。

问题：OrangeCLK 提高了对代写人选的要求，他们不仅都要和 OrangeCLK 关系好，彼此好感度也要超过 100 才行，否则可能会内讧。还是给出好感数据表和需要人数，问能不能找到这样的个人？

先来浇一盆冷水，傻×的 OrangeCLK 死活也找不到这个问题的多项式解法。于是他就捉急了，因为他的智商只能做多项式时间的运算。这时候有一位大神告诉他，咦，你挑这个人就 OK 啦。于是 OrangeCLK 开开心心地把大神给他的人方案一拿，把对好感度数据一查，果真，包括他本人在内的这个人彼此好感度都超过 100，我们看到这个数字显然是多项式的。大神给的人方案，就好比是一串验证辅助串，有了这样一串验证辅助串，由于图灵机对每一个数字大小判断的元操作也是多项式级别，我们就能构造出一台图灵机，基于输入，在多项式时间内验证是否属于。

所有可以借助验证串在多项式时间内验证的语言，组成了集合，对应的问题叫做问题。

中的是 nondeterministic 的意思，意指不确定机。不确定机和上文我描述的图灵机有一点区别，它表头的转换机制不是确定的，看到一组，它可能有几个不同的操作方式，而且每一步都有这样相同多样的操作方式，最后只要有一种碰上停止状态，整个程序就告结束。也可以理解为，所有可以被不确定机在多项式时间内判定的语言集合。和验证版本的定义等价。

我们很在乎多项式，因为多项式是我们可以承受的计算时间。多项式之上是指数，指数级的时间复杂度是几乎没有实际计算价值的。举个例子，如果一个问题对于长度为的输入串需要运行步，那么对于长度为 80 的串，这台图灵机就要跑步，，大概是全宇宙原子总数那么多，宇宙的寿命还不到秒。所以，多项式才意味着可计算，超出多项式，我们就当不会做。

很显然，是的子集，那么，和相等吗？存在一个语言属于却不属于吗？

这就是世界闻名的问题，是21世纪数学最重要的十大问题之一，五大问题之一，三大问题之一，一大问题之一。

太重要了，可也太难了，我们既找不到方法在多项式时间内就能判定 OrangeCLK 能否找齐代写论文的人，也不能证明这样的方法不存在。天下所有的问题，都像这幽灵一般让人捉摸不透。

NPC，问题归约

？哈哈，这可不是打游戏的时候遇到的 NPC，它的全名叫做 NP-Complete，中文雅号完全。和一样，也是一个语言的集合。

我们都聊到了，OrangeCLK 还在纠结找人代写论文的严肃问题。机智の OrangeCLK 发现，他面临的问题其实可以转化。如果把每个人都看成一个点，两人之间的好感度如果超过 100 就连一条边，如此我们就得到了一张数学意义上的图。原问题就转化为，能不能在这张图中找到一个完全子图？看到没有，一个偷鸡摸狗的作弊问题瞬间被转化成了一个高端大气上档次的数学图论问题。数学家们对这个问题可是颇有兴趣，可惜，要找这个问题的多项式解法？他们也不会做。记得我在探讨理论、算法、应用三者之间关系的时候怎么说来着？理论大部分时候都是没用的，它的“精髓”就是把一个大家都不会的问题转化为另一个大家都不会的问题。我们打小从数学书上就学着要化未知为已知，可是人生总是如此的艰难，现实中哪有那么多已知呢？在计算理论研究中，真的勇士，敢于面对惨淡的现实，敢于面对凶残的无知。科学家不断开拓新领域，做着化未知为未知的转化，这种工作，叫问题归约，同时也是在给问题分类。同一类的问题，具有相同的时空性质，整个类的问题都休戚与共同生共死。于是，一个问题得解或者是得证无解，就会推进许多领域大量问题的解决。不管问题我们现在会不会做，大家都致力于打通问题之间的任督二脉，这样在问题的茫茫荒原中，将来只要有一个旷古烁今的灵光一现，大批量的问题都会瞬间得到解决。敢于在一片未知之中闪转腾挪创造科学结构，需要多么大的胆略与魄力！这就是人类伟大的远见卓识壮志雄心。

我们看到，代写论文问题被归约到了完全子图问题。只要我们能在多项式时间内做出完全子图问题，我们也一定能在多项式时间内做出代写论文问题，因为这个归约过程本身的计算也是可以在多项式时间内完成的。

下面我要公布一个让你合不拢下巴的事实：所有问题都可以归约为完全子图问题。

啥？没震惊？那我换个说法，只要我们在多项式时间内解决了完全子图问题，天下所有的问题就都能在多项式时间内解决。没错，是所有！这样和就能画上一个大大的等号，21世纪最大数学难题就可以告破。

原来完全子图问题如此特别，我们有必要引进一个新的类型。刚才说了，计算理论的一项重要工作就是给问题分类。于是应运而生，中的任何一个问题得到多项式解决，就和相等了。

科学家们已经发现了一大堆问题，显然，它们非常争气，都没有被人类解决。

NP 难

这货英文名叫，我这篇文章，有一半动机都是为了这个坑货而写。

这玩意儿坑在哪儿呢？学术界到现在对于居然没有一个统一的定义！各个山头的大佬们众说纷纭各持己见。我今天就来努力梳理一下。

前面讲到我们只讨论判断题，判定问题。现在呢，我们可以考虑解答题了，专业叫法，搜索问题。

图灵机做判断题，无非是停机，并且停在一个接受/拒绝的状态上，根据停机状态来判定答案。而搜索问题要怎么应对呢？这需要图灵机在纸带上写出答案。输入“2+2”，要能输出“4”。简而言之，除了是/非类型的问题，就是搜索问题，意指在茫茫大海中寻找答案。

既然名字叫难，不说比还难，起码不能比容易。怎么度量难易呢？可以用问题归约啊，如果A解决了，B就也可以解决，我们是不是说B不会比A难？换言之，A 至少和 B 一样难。所以难是这么定义的：至少和中最难的问题——问题——一样难。如果一个问题可以在多项式时间内归约为另一个问题，那么就属于难。如果问题能在多项式内解决，则中的某个问题也能解决，进而所有问题都能够在多项式内解决。

乍一看和挺像，区别就在于问题类型。只包括判定问题，难可以包括搜索问题。有一些学派认为难包括普通的判定问题和搜索问题；有一些学派认为难还应该包括不可判定问题比如停机问题；还有一些学派认为难不应该包括判定问题只能讨论搜索问题。这些分类方法都有合理之处，最终谁将胜出，还看历史选择。

但是，总有那么些问题是大家公认属于难的，比如最大完全子图问题：给定一个图，求出它最大完全子图中有多少个节点。很显然，这是一个搜索问题，而且一旦这个问题有多项式解，完全子图也就不在话下了，OrangeCLK 的论文也就得救了。

这里宕开一笔，年幼时看科学，总觉得科学与艺术不同。艺术是审美和表达，充满了主观的想象与个人的判断；而科学是客观和真理，奠基于严密的逻辑和重复的实验。年岁渐长，见识益多，渐渐觉得艺术有十分客观之处，科学也有十分主观之处。审美是有一定普适标准的，音乐、美术、文学、戏剧，美好的作品总是蕴含着跨越种族跨越国界的共同感动。科学也根本不客观，科学的理论到底是建立在条条假设上的逻辑推导和计算演绎，不同人观念不同，持有的先验假设不同，构建出的理论体系也就不一样。相信哪个理论，选择哪个理论，是一件很主观的事，也是一件随着历史流变的事。艺术感动人心，科学可以证伪。这是二者在我心中最核心的价值。

计算理论的发展

刚才探讨的只是计算理论的基石，计算理论主要包括包括形式语言自动机图灵机、可计算性、计算复杂度三个部分。广义说来，算法设计、计算经济学、计算生物学、机器学习理论等都属于理论范畴。刚才我们探讨了计算复杂度的时间维度，事实上也有空间复杂度的相关研究，类似于时间，我们有(PSPACE)，(LOGSPACE)（简称L）等复杂类。

除了图灵机外，另一个常用的计算模型是电路，研究电路的复杂性很多时候比图灵机方便实用，这也是研究的重大方向。

姚期智教授提出了通信复杂性这个领域，描述交换信息、多机器共同运算的复杂性。

现实生活中由于很多问题得不到完美的解决，人们创造性地发明了很多近似算法和随机算法来解决问题。这些算法不一定能得到最优解，但是离最优解差得不远。那么为了度量算法解和最优解的差距，为了度量得出正确解的概率，为了给这些算法一个理论基石，关于近似算法和随机算法那的理论研究也就顺理成章了。

除了电路、通信、近似、随机，广大理论计算机科学研究者还在努力开拓新的领域，把问题归约到越来越遥远的地方。虽然大部分难题都尚未取得进展，但是已经阐发出很多实用算法，对我们的世界改变良多。

量子计算理论也有不错的发展，取得了一系列诸如这样的重要结果，全球各大高校和公司也都在加紧制造量子计算机进行量子计算的实验。清华大学交叉信息院量子信息中心（CQI）在这一领域卓有建树，部分方向领跑全球。

就我个人看来，物理理论也好，计算理论也好，都基于数学但是有超出数学的部分。给全所有定理，数学也无法预测复杂系统的运动情况；给定所有运算规则和其实状态，数学也未必能预测某些问题的计算结果。计算领域和物理领域一样，有一些数学无法解释预测的现象。很多数学家不相信的东西，我们可以选择去相信、去实验。在数学力所不及的地方架起计算理论的新结构，发现计算的规律，是一件多么具有挑战性的事啊！

鸣谢

• 感谢 John Steinberger 的 Brutal and Swift Introduction to Computer Science课程。
• 感谢Michael Sipser的名著Introduction to the Theory of Computation。
• 感谢课程指导老师王跃宣。
• 感谢与我讨论NP-Hard定义的寿鹤鸣。
• 感谢段萌软提出她对理论的看法。
• 感谢读者！