主题：Kevin Buzzard：计算机做不到什么？ -- 万年看客

https://www.youtube.com/watch?v=jQPb7DRMoZY&list=FL3RezzS-A7eu0NV9aDxzpdA&index=55&t=0s

杀手机器人如今已经是现实了，所以你有必要了解一下。杀手机器人有两大特征，首先能杀人，其次是机器人。但其实还有第三大特征：杀手机器人由人类控制，至少目前为止是这样。大家可以到Youtube网站上找一下波士顿动力公司在2003年10月上传的杀人机器人视频，非常精彩。这台机器人在公司停车场上跑了八分钟，偶尔会经过一位肥胖秃头的操作员。归根结底，关键不在机器人，而在于手拿遥控器的操作员。现在的问题是，计算机能控制这台机器人吗？既然计算机倾向于让人类失业，那么计算机能控制杀手机器人吗？事实上我们还可以更进一步，编写一个应用程序，只要下载到手机上，输入某人姓名，轻轻一点，某个地方就会释放出一台杀人机器人替你去杀人。计算机能做到这一步吗？

为了制造这样一台杀人机器人，一个公司需要满足哪些条件呢？首先，这个公司需要一个足够大的数据库，装下几十亿人的姓名、住址与日常活动规律；其次，我们需要能够写出这个应用程序的程序员；然后，我们需要高水平的人脸识别软件，以免机器人杀错人；第四，我们需要操纵这台机器人离开停车场冲向目标；第五，我们需要整整一支军队的杀手机器人。那么目前有哪家公司满足所有这些条件呢？谷歌怎么样？谷歌掌握着几十亿人的姓名、住址与日常活动规律吗？绝对的。就算你不用安卓手机或者干脆没有智能手机，你的上级、同事、妻子或者孙女也会将你的地址与联系方式添加进他们的安卓手机联系人名单里。这份名单会与谷歌同步，然后谷歌就知道你姓甚名谁家住哪里电话号码多少了。谷歌手下有高水平程序员吗？绝对的。谷歌有人脸识别软件吗？绝对的。我只要在安卓平板跟前露个脸，平板就自动开启了。谷歌有驱动机器到处走的程序吗？绝对的。别忘了现在谷歌正在花大钱研发无人驾驶技术。

所以现在就只剩下了一个问题：谷歌有没有一支杀手机器人军队呢？谷歌的格言曾经是“不作恶”，可是在2015年他们悄悄地将这条格言撤掉了。（笑声）接下来还有一条看似不相关的进展：2015年12月，谷歌收购了波士顿动力以及其他七家机器人公司。所以这些杀手机器人一下子全都变成了谷歌的财产。谷歌现在有多少杀手机器人呢？支持一个应用程序应该是够了。事实上我觉得理论上谷歌内部的某人绝对可以写一个应用，只要输入姓名就能派遣若干台杀手机器人去杀人——当然还要做些实验来确定多少台机器人保证够用。这是一件计算机能做到的事情，所有的必要条件都齐备了。

那么再问一个问题：假如谷歌有了自我意识，不再需要人类来写应用程序，或许计算机本身就能写应用程序，或许计算机可以决定要接管世界，或许计算机真打算这么做。但是我对此不敢太肯定，因为这意味着计算机有能力思考，而我不确定计算机究竟有没有能力思考。所以说计算机能做到的事情是在有人写好程序的前提下运行程序去杀人，做不到的事情——在我个人看来——则是思考。

现在画面上左边这位是1997年全球国际象棋冠军加里.卡斯帕罗夫。画面右边是一台在当时很先进的电脑显示器，显示器连接着一台名为深蓝的计算机，由IBM公司制造，是当时最高明的象棋机器人。人类冠军与计算机冠军在1997年进行了一场比赛，共计六局。卡斯帕罗夫输了比赛，1997年就此成为了计算机在象棋领域超越人类的标志年份。从那以后计算机的象棋水平日益提升，如今但凡还有理智的人都不会挑战计算机下象棋了。那么在这幅画面当中究竟是谁在思考呢？卡斯帕罗夫显然看上去像是在思考，摆出了西西里防御定式，显然正在考虑最佳步骤。他运用了自己的直觉、洞见与经验。他还玩起了心理战术，尽管他的对手是计算机。他曾经与这台计算机交手过，知道对方惯于采用怎样的布局，不擅长怎样的布局。他正在努力调整自己的打法来战胜计算机。那么画面右边的东西正在干什么呢？正在思考吗？我不觉得这东西正在思考。计算机擅长什么？计算机擅长非常迅速地遵从指令。我认为这并不等同于思考。

计算机遵循的基本逻辑指令就是程序。接下来我要告诉大家一点关于计算机与程序的事实，我会尽可能把话说得直白一些，同时还要讲清楚几个难点。关于计算机我要说两点。首先，计算机有内存，用来存放信息。有时计算机在进行计算时需要查询此前其他计算的答案，这就需要内存。计算机程序就存放在内存里面。其次，计算机需要处理器。处理器会读取程序当中的指令并且逐条执行。目前最先进的处理器是4G级别，我们的手机里安装的就是这种处理器，每秒钟能执行四十亿条指令。早在1997年，深蓝就能每秒钟分析两亿步象棋棋招。所以深蓝会尝试所有的棋招，哪怕是看上去很可笑的臭棋，例如将上一步移动过的棋子再移回原位。深蓝会做出各种猜测来估计接下来怎么走看上去最好，但是卡斯帕罗夫并不会这样行棋。绝大多数可能的棋招卡斯帕罗夫根本不会考虑，因为他具备直觉。但是直觉终究被每秒几亿次的暴力穷举打败了。我们也终于证明了计算机下象棋可以比人类更强。

尽管如此，我依然不认为这是思考。我不认为因此就有必要担心机器人暴走将人类全都杀光。我之所以不认为深蓝在思考，是因为我经常洗碗。我要将碗碟放进洗碗机，洗完了还要拿出来。清空洗碗机是一个高度机械化的过程。盘子要放在盘子该在的地方，碗要放在碗该在的地方，刀叉要放在刀叉该在的地方。我在摆放的时候根本不动脑子，每次都遵照同样的顺序，因为我想在某些方面效仿计算机。我在装洗碗机的时候不会思考动作，而是在后台思考其他问题，例如数学问题，待会怎么吃饭，或者洗完碗之后干点啥。机器人也能装填洗碗机，可是装完了就完了。

下面我们看看几个问题以及这些问题能否得到解决。到现在为止我谈到的问题都非常困难，例如编写一个能释放杀人机器人的应用程序。这是一个极其困难的工程学问题，因为涉及的部件非常多。击败国际象棋冠军同样非常困难。想要搞清楚计算机究竟会不会思考更是难上加难，很多人都有不同观点。因此为了取得进展，我们要先谈一下比较简单的问题。我想暂时先忘掉计算机，转而谈谈问题是什么，如何解决问题，以及怎样确定某个问题究竟有没有得到解决的可能性。下面就是一个古希腊人最早提出来的问题：尺规作图能否二等分一个角。这是一个已经有两千年历史的问题，可以追溯到欧几里得那会儿。首先，将圆规尖端固定在角的顶点，画一道圆弧与角的两边相交。可以确定，两个交点到顶点的距离是一致的。然后将圆规尖端置于两个交点，用同等距离各画一道圆弧并使其相交。然后将交点三与交点一二分别相连，然后角的顶点、交点一二以及交点三就形成了一个菱形——这是公元前三百年欧几里得手稿里记录的解法——然后连接顶点与交点三，这个角就被二等分了。就这样我们证明了一条数学定理：尺规作图可以二等分一个角。为什么？因为我刚刚做到了，还讲解了这套做法。

接下来是另一个古希腊人提出的问题：尺规作图能否三等分一个角？你可能会觉得既然能二等分那么肯定也能三等分，可是古希腊人却没能搞定这个问题。直到1837年才有一位皮埃尔.万芝尔证明了不可能三等分。两个问题看上去差不多，二等分和三等分就差一个字。但是我们通过实际操作解决了前一个问题，却要等待两千年才能通过证明不可能来解决后一个问题。但是古希腊人却并不认为这个问题不可能，只是觉得自己做不到。

可是究竟要怎样才能证明某件事情不可能做到呢？万芝尔掌握着哪些古希腊人没有的数学工具呢？古希腊人开创了几何学，也开始着手研究算术，不过他们在这两个领域之间完全没有建立联系。他们手里没多少抽象数学手段。到了十九世纪初万芝尔的时代，数学家们已经掌握了0的用法——古希腊时代所有的数字都是正数——发明了负数，还拥有了笛卡尔坐标系。勒内.笛卡尔提出可以用x轴与y轴的坐标来表示平面上的一点，于是从来都只是几何概念的点突然具备了算术意义。这就是古希腊人不具备的几何与算术之间的联系。今天我们使用坐标系就像天经地义一样，可是却需要一位笛卡尔这样的天才才能发现坐标系的存在。此外，数学家们早就发现了加减乘除四则运算，但是在十九世纪科学家们有了域的概念，确定了只有有理数才能进行四则运算。更进一步，他们还有了维数的概念，既假如一个域包含的数字总量比另一个域更多，那么较大的域的维数就比较小的域更高。这里谈论的不是现实世界的空间维度，而是有关自由度的抽象数学概念。利用这些抽象的数字域，数学家们可以构建某些维数极大的抽象物体。这些概念都是在过去两千年里发展起来的。

有了这些工具之后，万芝尔意识到不仅不可能依靠尺规作图三等分任意角，甚至都不可能三等分60度角。我不想太详细地解说他的论证，以免大家觉得无聊。根据我给大三学生们教授伽罗瓦理论时采用的简略解法，他将几何问题转化成了算术问题，最终证明尺规作图能够生成的规矩数的坐标体系的维数相当于2的乘方，例如1、2、4、8等等。三等分60度角产生的数字体系的维数是3，不是2的乘方，所以不可能通过尺规作图来完成。总结一下，欧几里得证明了尺规作图能二等分一个角，万芝尔证明了尺规作图无法三等分一个角。数学家们证明某事可行只要做一遍就可以了，但是要证明某事不可行却需要分析远远更加深刻的根由。万芝尔使用了现算术学工具，解决了古希腊的问题，这一成就证明了现算术学工具的有效性。数学就是这样，一个问题往往需要几百年才能得到解答，解答问题所必需的工具在提出问题时往往还不存在。

回过头来再说计算机。画面上这位是全世界第一位程序员阿达.勒芙蕾丝伯爵夫人。之所以尊奉她为全世界第一位程序员，是因为她撰写了全世界第一个计算机程序。当时有一位查尔斯.巴比奇，此人与其说是数学家，倒不如说是工程师。他设计了一台机器，名叫差分机。这是一款非常原始的计算机，通过拨转旋钮来编程。巴比奇在意大利进行了关于差分机的演讲，有人用法语做了笔记，这本笔记流落到了勒芙蕾丝手里，她又将笔记翻译成了英语。在翻译过程中她理解了巴比奇的思路，并且在译文最后添加了一系列附注。在编号为G的最后一条附注当中，她举了一个例子：只要按照特定方式调整旋钮，就能让差分机计算伯努利数。当时的计算工作还需要某人坐下来用纸笔完成，而伯努利数又特别难算。但是按照勒芙蕾丝的构想，差分机完全可以自动计算伯努利数，免得某人费事。因此我们可以将以下定理记在她的名下：计算机可以计算伯努利数。证据则在于她写了一个能做到这一点的程序。不过勒芙蕾丝从没见到自己的设想成为现实，因为巴比奇差分机受到技术问题限制，从没有真正问世。等到技术问题解决时，巴比奇的资金也耗尽了。至于勒芙蕾丝本人则在三十六岁就英年早逝了。当然，在那之后还是有几位宅男实现了她的设想。

我想有心的听众们已经能猜到接下来故事的走向了。再快进一百年，来到艾伦.图灵的时代。图灵也想过计算机的问题，但是图灵不是工程师，而是数学家。因此他设想了计算机的数学模型——有点像利用算术来研究几何。此类模型今天被人称作图灵机。图灵机为后来的数学家们打开了大门，让他们能够证明计算机是否能完成远比计算伯努利数更加深奥的问题。麻烦在于，假如要证明计算机能做到某事，只要写个程序就行。可要想证明计算机做不到某事，证明过程则要困难得多。勒芙蕾丝孤立出了一个有趣的抽象问题——即计算伯努利数——并且证明了计算机能够做到。图灵同样孤立了一个有趣的抽象问题，但是由于他手里的数学工具比勒芙蕾丝更多，因此他从反面入手证明了计算机做不到。那么你难道要检查世界上过去现在将来的一切电脑程序能不能解决这个问题吗？接下来我想向大家解释一下图灵的证明方法。首先，1936年图灵研究这个问题的时候世界上还没有计算机。最早的计算机是二十世纪四十年代出现的，图灵还参与了好几款计算机的研发。但是图灵在一台计算机都不存在、一个计算机程序都不存在的1936年就证明了这个理论。他对于计算机死机的可能性很感兴趣。死机自然很讨厌，会让你损失数据与信息，不得不重启计算机。图灵则早在计算机问世之前就预见到了死机的可能性。

画面上是一个用伪代码撰写的计算机程序。程序的运作方式是从这一步进行到下一步，除非接到其他指令。

1：用户输入一个数字。

2：设定该数字为X。

3：若X等于7，执行步骤4；否则执行步骤6.

4：执行步骤5。

5：执行步骤4。

6：在屏幕上显示“你好”字样。

7：结束。

好比说你点击了手机上的一个应用，随即弹出一个小窗口要求你输入一个数字。你随便输入了一个53，然后小窗口就消失了。53不等于7，所以我们跳到步骤6，屏幕上出现“你好”字样，然后程序的运作就结束了。但是假如你输入的是7，在第二步X等于7，于是跳到第五步，然后第五步又跳回第四步，如此不断循环。由此你就能看出来计算机并没有在思考，因为人类循环上几次就会觉得烦了，但是计算机却会永远循环下去，无知无觉地遵循指令。假如你的操作系统陷入这样的循环，那么你的计算机将会无视键盘与鼠标的输入，你再怎么敲键盘点鼠标也不会有反应。这时你只能重启计算机。在这个模拟程序当中，只要输入7就会导致计算机死机。

……

想要确定某一个计算机程序是否会陷入无限循环是一个非常复杂的逻辑谜题，而计算机恰恰又是解决逻辑谜题的最得力工具。所以图灵决定写一个程序来检查其他程序是否会陷入无限循环。既然无限循环与死机是坏的，那么我们可以将一个会陷入无限循环的程序称作坏程序，将一个不会陷入无限循环的程序称作好程序。图灵提问道：“怎样才能确定一个计算机程序是好的呢？”他在1936年的论文当中对计算机进行了抽象公理化的数学定义，因此现在他可以依靠数学来解答这个问题。他写了一个程序，这个程序的输入并不是一个数字，而是另一个程序。假如这是个好程序，图灵程序的输出就是“好”，反之则输出“坏”。

这一来情况就有趣了，因为你也可以将图灵程序输入到图灵程序当中去。图灵意识到，如果你能写一个区分好坏程序的程序，那么你也可以写一个完全扯淡的程序K。如果将好程序输入进去，程序K就会表现得像个坏程序；如果输入一个坏程序，程序K就会表现得像个好程序。换句话说，如果输入一个坏程序，程序K就会自动停止；如果输入一个好程序，程序K就会故意陷入无限循环。那么假如将程序K输入其自身呢？最终结果是好是坏呢？假如K是好的，那么K一定是坏的。假如K是坏的，那么K一定是好的。一个程序肯定不可能既好又坏。这其中的关键在于图灵一开始的假设就是错的，我们不可能写出一个区分好程序与坏程序的程序。在图灵的推理当中，这个假设是唯一无法依靠逻辑来证实的部分。因此图灵得出结论：我们不可能写出一个为其他计算机代码捉虫的程序，因此计算机死机是不可避免的。当然，图灵在1936年的具体证明过程要比我们这里严密得多，我只是讲解了一点皮毛而已。我想要强调的是，图灵借助数学抽象理解了计算机。

在我看来，图灵居然能证明某件事情不可能实在是太了不起了。在数学当中，人们经常要在他们感兴趣的领域解决问题，也经常会遇到看似无法解决的问题。有时这些问题最终能够得到解决，另一些时候这些问题的确无法解决。我们见过了纯数学方面的例子，也见过了理论计算机科学方面的例子。这里的“理论”二字尤为突出，因为图灵机在实践方面的问题很大。今天计算机确实已经存在了，而且主导了我们的生活，所以现在我要谈一下计算机在实践方面遇到的问题。

首先，图灵机具有无限大的内存。数学家们全都习惯了与无限打交道，自然数的个数就是无限的。其次，图灵并不关心计算机的处理速度，只关心计算机是否会陷入无限循环。假如某个循环能在一百万年后结束，假如你的鼠标能在一百万年后突然恢复功能，那么在图灵看来你的计算机就没有死机。在实践当中，计算机内存必须由物质组成，例如传统硬盘里面就有许多微小的磁铁，固态硬盘里则有很多微小的电路。任何存储单元如果想要在我们这个宇宙里存在，就必须具备物理形态，因此也会与抽象的图灵机相去甚远。因此最起码我们需要一个粒子来充当内存。不幸的是，宇宙当中的粒子总量仅仅是10的80次方。这一数字决定了任何计算机的内存上限。此外，量子力学指出物质在微观层面的表现十分怪异。根据目前的主流量子力学理论，存在一个具有讨论意义的最小距离，即普朗克距离。假如你相信相对论，信息无法以超过光速的速度传播。因此光走完一个普朗克距离所需的时间被称作普朗克时间。这个时间是10的44次方之一秒。在小于普朗克时间的时间里，任何计算机都无法完成任何运算。

另一方面，我们只对能够在地球上存在的计算机感兴趣，而地球再过几十亿年就不宜居住了。就算是存在于宇宙当中的计算机，等到宇宙热寂那天也肯定无法继续计算下去了。更现实一点的话，几十亿年后太阳肯定要变成红矮星，到时候大海都要煮开了。这些实际条件限制了任何计算机能够执行的指令条数上限。简而言之，假如某个程序需要存储的数字个数超过某个极大数量，需要执行的指令条数超过某个极大数量，那么任何地球上的计算机都无法运行这个程序，至少无法在地球化为毫无生气的空壳之前运行完毕。

图灵从没想过要遵守这些限制，他也根本不关心这些限制。当时正是战争时期，他还有很多别的事要操心。但是对于我们来说，现在的问题不仅仅是“计算机能否解决某个问题”，还有“计算机能否足够快地解决某个问题”。以下是两个非常简单的程序。程序一是这样的：

1，用户输入一个数字。

2，设定该数字为X。

3，打印出X。

向这个程序输入53，就会打印出53。程序二看上去与程序一差不多，其实却有一点差别：

1，用户输入一个数字。

2，设定该数字为X。

3，打印出X个0。

不要忘了，53这个数字是有意义的，意味着53件东西。因此程序二输出的是输入结果的含义。现在我们让程序一与程序二比一下运行速度，谁会赢呢？肯定是程序一，因为程序二的工作量要大得多。当然，从实践角度来说，两个程序都能在一眨眼时间内运行完成，所以你注意不到差别。但是程序二还要应对数据缩放的问题。假设我们输入的并不是53，而是531。程序一只需要多打印一个数字就够了，而程序二需要打印的数字个数却是53的十倍。换言之，在输入数据略有波动的前提下，程序一很容易就能应对，程序二从处理时间则会增加若干倍。在现实世界里，输入数据经常会增加，而你肯定不希望你的程序因此而陷入停滞。比方说我想写一个程序来为全校学生安排考试时间，由于每一位学生的选修课程都不一样，必须保证任何一位学生都不必在同一时间参加两门课程的考试，同时所有考试的时间还必须尽量集中。当然我们现在就有解决这种问题的程序，我们希望这个程序更像程序一而不是程序二。

以上我对数据缩放的讨论很不规范，数学家们早就针对这一概念进行了更加规范的描述。如果你研究一下历史，人们最早开始关心计算机完成某事的速度而不仅仅是抽象的计算机能否完成某事是在1955年，相关记录是一封信，发信人是《美丽心灵》的主人公约翰.纳什，收信人是美国国家安全局。他在信中指出，关键不在于计算机能否解决某个问题，而是在于计算机解决这个问题的速度。按照纳什的说法，假如某个计算机程序能在多项式时间内运行，那么这个程序在数据缩放方面就像程序一。当然这种说法并不规范。规范说法是：假如某程序的功能可以用多项式函数P(n)来表达，那么这个程序就可以在多项式时间内运行。假如你向这个程序输入一个n位数，那么这个程序至多只需要P(n)步就能完成。在实践当中，多项式时间程序就相当于编程界的圣杯。假如你的问题可以在多项式时间内解决，那么十有八九早就有人编写了能够有效解决这个问题的程序。所以我们现在的兴趣不仅在于计算机能解决哪些问题，还在于计算机能够迅速地解决哪些问题。数学家将所有能够被计算机迅速解决的问题统称为P。

接下来我们看看密码。假设你与朋友约定了一套密码，别人都不知道密码是什么，那么你就可以与朋友收发加密信息。如今的加密就没这么简单了，因为我希望我的手机与电脑能够与任何其他终端收发信息。假如我的电脑打开了一个从没打开过的网站，那么我的电脑就要与另一台从未接触过的电脑交谈。我兴许还需要向另一台电脑发送我的信用卡号码。总之我需要发送加密信息，可是两台电脑之间却没有预先约定密码。这就麻烦了，因为互联网上的人们都能听到你在干什么。你的服务商肯定知道你在干什么，政府很可能知道你在干什么，其他人也能看到你的电脑收发文件包。一般的密码已经不好使了，我们这里需要的是公钥加密。我需要保证就算我的邻居安装了wifi侦测器，能够看到我收发文件包，也依然无法得知我的信用卡密码。令人惊奇的是，早在二十世纪七十年代公钥加密技术就被发明出来了。这一技术的核心在于利用非对称性，也就是要让加密比解密快得多。我举个例子来说明非对称性是什么意思。比方说我有一截棉线，给你两分钟时间在棉线上尽可能多地打结。两分钟之后这根棉线肯定会纠结成一团。绳结将会相互纠缠在一起，最后棉线将会变成一个极难解开的线球。打结很容易，解开就难了。并不是不可能，但是肯定需要远远超过两分钟的时间。

有趣的是，乘法运算同样也是不对称的。比方说43乘以61等于多少？答案是2623。得出这个答案需要多少步？1乘3,1乘4,6乘3,6乘4，整个运算过程在十步之内就完成了。这个算式当中最小的数字是43，但是计算过程根本用不着43步。因此乘法的缩放很容易。那么对乘法进行逆运算又会怎么样呢？2183这个数字是哪两个数字的乘积呢？是2吗？不是，2183除以2得到1091，余数是1。是3吗？也不是，得到727，余数是2。你就这样一直除下去，直到37，这才发现可以整除，结果是59。这个计算过程的缩放就很困难，因为答案当中包含37，所以就要耗费37步运算——当然，一开始我们并没有用1去除2183，实际上用了36步。我们将这个过程称作因数分解。目前所有公开的因数分解方法全都缩放得很差。换句话说，因数分解不能在多项式时间内完成。假设我们找来两个极大的质数，各自有一百位数，将两者相乘，大约需要两万步就能得出结果。但是一百位数是有意义的，在1后面写一百个0只是个很聪明的计数法而已。要知道全宇宙的粒子数量加在一起也不够一百位数。换句话说我们无法通过逐次做除法的方式算出这两个质数，因为宇宙不够大。这样的因数分解运算至少无法在我的一生里完成。如果用大质数来制作密码，那你就用不着担心人家破译，反正破译出来的时候你早就死了。

但是因数分解还有一个很有趣的特性。假如某人交给你两个一百位数字，让你验算它们是不是正确的因数，那么计算机只需要一眨眼就能完成，只要把两个数字相乘，然后看看结果对不对就行了。因数分解很难计算，但是却很容易验算。在现代计算机复杂性理论当中，易于验算的特质是另一个重要理念，因此我们专门给这个理念起了个名字。NP指的是一切能够快速验算——也就是在多项式时间内验算——的问题的集合。所以说，P是一切能够快速计算的问题，NP是一切可以快速检验答案对错的问题。如果一个问题属于P，那也一定属于NP。但是很多属于NP的问题我们却无法快速解答。大数字因数分解属于NP，为考试安排时间表也是。我家有三个初中生，市议会每年11月给家长发一张申请表，你填完表之后要到来年3月才能让孩子入学，中间四个月时间都要用来计算如何为每所学校都安排数量正确的学生。其他例子还有寻找最符合某一套序列碎片的DNA序列，为相变的伊辛模型确定基态——这两句话我都不知道是啥意思，不过看着挺重要的，我就添加在这里了——以及通过标准互联网协议不借助密钥对于发送到某个安全网站的数据进行解密。消消乐是NP，宝可梦对战是NP，超级马里奥通关还是NP。上述问题全都属于NP，但我们不知道它们是否也属于P。

接下来的问题是：P是否等于NP呢？如果某个问题我们能够快速验算，那么是否也能快速计算呢？1971年，斯蒂芬.库克率先提出了这个问题。他对这个问题进行了严格的数学定义，为后来的研究打下了基础。不过这一年他没能得到伯克利大学的终身教职，因为当时计算机领域实在无关紧要。如今这个问题却成为了克雷数学研究所的七个千年大奖问题之一，企业界为每个问题都设置了百万美元的奖金。假如真有人证明了P=NP，接下来会怎么样呢？那就意味着我们突然可以迅速解决此前的许多难题了。交通安排将会得到最大程度的优化，人员物资的流转将会更加快捷廉价；工厂生产速度将会极大提高，浪费将会减少；药物研发领域将会突飞猛进；计算机将会具有完美的视觉辨识与语言辨识能力；天气预报与地震预报能力将会极大提升；计算机对于数学定理论证的辅助作用将会极大加强。数学证明题是最典型的NP问题。你面对一个问题，手头有一大堆公理不知该用哪一条。但是如果有人将证明方法给你看，你很容易就能确定这套方法对不对。最后，现行的加密法都将失效，政府将会毫不费力地解读你的电子邮件；互联网安全就此成为过去，你将再也不敢向购物网站输入信用卡密码，在线银行业也会崩溃。简而言之，互联网会被废掉，不过我们兴许能治愈癌症。无论如何，这个世界都将改头换面。

不幸的是——或者说幸运的是——绝大多数计算机科学家都相信P不等于NP。即确实存在容易验算但难以解决的问题。因此现在我们很确定我们可以进行加密交流。我大概能确定政府不能破译我发送的信息，恐怖分子大概能确定政府不能破译他们发送的信息，所有在暗网上贩卖毒品军火的人们大概也能确定政府找不到他们。类似案例发生过不止一次，警方很确定某个加密设备里面存放着足以将某人定罪的信息，但是却破译不了。因此确定P与NP之间的关系的确事关重大。那么数学家究竟怎样才能证明P不等于NP呢？他们必须找到一个NP问题并且证明任何计算机程序都无法迅速解决这个问题。目前我们还没有足够的理论工具来做到这一点。纳什给出了可以迅速解决的P问题的例证，库克规范了相关的数学规则并且提出了P与NP的困难问题，而目前我们在这条路上已经走到头了。未来或许某一天确实有人能提出一个易于验算并且通过数学证明了无法迅速解决的问题，但是这一天还没有到来。欧几里得的难题花了两千年才得到解决，我们的问题需要多少时间呢？当代的数学技法在这个问题面前已经全都败退了下来。有一次看起来挺有希望的尝试，源自2001年，兴盛于2011年，采用了几何复杂性理论，也就是二十世纪六十年代才出现的现代代数几何与表示理论。这方面的重大突破发生在去年4月，有一队人马证明了几何复杂性理论无法用来解决P与NP的问题。话说到这里，我们究竟怎样才能证明计算机无法迅速解决某个问题呢？目前我们还没有答案。谢谢大家。