价值百万美元的问题 – P vs NP 问题 (音频讲稿)

大家好,我是大老李。今天跟大家聊聊算法复杂度(Complexcity)问题。学过计算机算法课程的听众肯定听说过“多项式复杂度”,“指数复杂度”这些名词,还有著名的“P vs NP问题”。本期节目就来聊聊“P vs NP问题”。
首先,要说明几个概念。要讨论复杂度问题,首先要考虑的就是如何衡量一个算法的复杂度?你能想到的第一个指标应该就是时间。在同样的计算能力下,一个算法执行的时间时间越长,我们感觉上这个算法就应该越复杂。这是对的,但是不同的算法直接比较运行时间似乎又是不合理的。比如一个求一些数的最小公倍数的算法和一个对10个数字排序的算法,你光比较时间的话,你很难说哪个算法更复杂,因为这就是两个不同的问题,没有可比性。

所以计算机科学家使用另一个标准,就是当一个算法随着计算量的变化,所需计算次数的变化程度。比如,排序问题。排序问题本身有很多种不同的算法,这些算法之间应该是可以比较好坏的。人们发现,决定算法时间效率的根本问题在于,当一个问题规模扩大时,算法循环执行的次数。比如一个算法处理100个对象时,需要1分钟,那么处理1000个对象时,到是需要10分钟,还是100分钟,还是2分钟,这时就能看出算法的效率区别。
因此人们就开始分析,一个问题随处理对象增加时,算法消耗时间的增长速度。比如在“冒泡排序”算法中,算法操作时间是随着按排序对象的平方增加的,称为

的时间复杂度,并且人们发明了“大O”记号。冒泡排序的算法复杂度就用符号

表示。意思是如果排序16个对象需要x秒,则排序32个对象大约需要4x秒。而最快的排序算法,“快速排序”的时间复杂度是

,意思是如果排序16个对象需要x秒,则排序32个对象大约需要

秒。通过以上分析,我们就能看出快速排序要比冒泡排序效率高。
算法时间估算过程: 假设计算冒泡排序每次运算需要k秒,则因冒泡排序是

时间复杂度,且对16个对象排序需要x秒,则(大致)有:

则对32个对象排序所需时间是:

对快速排序,则有:

,则可以推出:

而在那么多复杂度中,人们发现大多数算法可以分为两大类,一大类中,这种算法的复杂度在大O符号中, 括号里是一个n的多项式,比如之前的冒泡排序,

就是一个n的多项式。这种情况下,人们称这种算法的复杂度为“多项式时间复杂度”。
而另一大类则n处于指数位置上,比如

的复杂度,这种情况下 ,称这个算法具有“指数时间”的复杂度。“指数时间”的复杂度显然比”多项式时间” 复杂度要复杂很多,因为

增长速度是非常快的。
另外,在之前提到的快速排序算法中,它的时间复杂度

也被归为多项式复杂度算法。因为

虽然不是典型的多项式,但它比大多数多项式的增长速度都慢,所以也归类到多项式复杂度中。
还有一点,虽然“多项式时间”、“指数时间”这些术语都是衡量一个算法所需时间的增长速度,但为了表述简便,我们有时也说“这个程序需要多项式时间”或者“需要指数时间”运行等等。但你要知道,这其实是说这个程序的随问题规模增加,其运行时间的增长程度。
以上,我们简单介绍了一下时间复杂度,那么我们可以开始聊聊什么是“P vs NP”问题。“P问题”是一类问题的总称,这类问题的定义是这样:如果一个问题存在一个多项式时间算法求解,则这个问题就是一个“P问题”。
其中的“P”是英语“多项式”一词:polynomial的首字母。典型的P问题就是比如之前提到的排序问题。还有一个问题是质数判定问题,给定一个整数,请判断它是否为质数。2002年,印度研究者发现了一个素数判定算法,其算法复杂度为

,因此正式确认了素数判定是一个P问题。

你可能推测“NP问题”就是指所有不存在多项式算法时间的问题,或者就是“指数时间”问题,但这是一个误解。NP问题的定义是这样的:如果给你一个问题和这个问题的某个解答,存在一个多项式时间算法验证这个解答的正确性,则这个问题就是一个NP问题。听起来有点拗口,我们还是可以举个例子看看什么是验证解答:
给你一个整数和另一个比它小的整数,请你判断这个小的整数是否是之前那个整数的因子,那你当然可以简单的去除一下,看看是否整除,这当然是多项式时间内可以完成的。
到这里,你是否发现一个情况:一个问题如果是P问题,则它必然也是NP问题。 比如给你一系列整数,问你这些整数是否从小到大排序好了?那我可以就用快速排序法,对这些整数进行一次排序,然后看排序结果是否与你给定的顺序一致就可以了, 而且肯定是在“多项式时间内”完成了结果验证,所以排序问题是“NP问题”,虽然我用的判别方法很蠢。
以上证明中用到的就是数学中的“化归”思想,就是将一个问题转化成另一个问题的过程。通常我们是设法将一个未知问题转化为一个已知解法的问题,这样未知问题就可以用已知方法解决。
那我们用“化归”思想证明命题–“所有P问题都是NP问题”:
对给定的一个P问题,用这个P问题的求解算法求解一次,然后与给定答案比较。则肯定能在多项式时间内,判定这个答案是否正确,所以P问题就化归为NP问题,即所有P问题都是NP问题。
这意味着,如果问:这个问题是P问题还是NP问题?这个问题是不太对的,因为如果这个问题是P问题,那么它也是NP问题。但我们为什么还会这么问?那是因为我们“默认”存在一些NP问题,它不存在多项式时间的求解算法,也就是它不是P问题。
为什么要说“默认”二字?因为这是没有证明过的事情。如果你能确切的证明某个问题存在多项式时间内的验证算法,又不存在多项式时间内的求解算法,那么恭喜你,你解决了克雷数学研究所提出的千禧年七大数学难题之一,即P与NP问题,并可获得百万美元的奖金。

当然,你可以反过来证明NP问题就是P问题,即NP与P互相可以“化归”,那么你同样也算解决了这个问题,尽管这看上去非常不可能。
那我们来举些例子,看看我们默认了哪些问题是NP问题,而不是P问题。
第一个问题叫“三色着色问题”。你可能知道有一个“四色定理”,它说:“任何一副地图都可以用最多四种颜色着色,使得任何相邻两个区域有不同的颜色”。那现在给你一副地图,问你“这幅地图能不能用三种颜色着色,使得任何相邻两个区域有不同颜色”,当然,有些地图是可以做到,也有些地图无法只用三种颜色着色。人们发现,找不到一个多项式时间算法,可以肯定找到一幅地图的三色着色方案,所以,它看上去不是P问题。

但是如果我给你一副已经用三种颜色着色的地图,问你这是不是一种合理的着色方案,这个问题就太简单了,你可以简单检查所有相邻的区域,看是否存在相邻区域用同一种颜色。如果不存在,那么这就是一个合理的着色方案。这种检查,是可以在多项式时间里完成的。所以“三色着色”问题是一个NP问题。
第二个例子可以叫“整数求定和问题”。给你一大堆整数,问是否可以从中找到若干整数,使它们相加之和是0,或是其他任何一个给定的整数?你会发现,你不能找到一个多项式时间来求解。
以下这些整数中,存在若干数字之和为0吗(大老李也不知道)?
91 74 -2 -86 75 21 50 -88 -22 26 -27 -16 -5 -89 -30 -4 85 50 73 -29
第三个例子,我给它名叫“小圈子问题”,这个问题是有关社交网络的。假设我给你一大群人的社交网络数据,比如这些人的微信账号,以及这些人之间谁与谁是微信好友。现在我的问题是,你能否从中找出一些小圈子?比如:能否至少找出至少6个人,这6个人与其他所有人都不是好友?如果有的话,那么这6个人就构成了一个小圈子。但是,你稍微思考下,要找出这样的小圈子,多项式时间算法是没有的。
另一方面,给你6个人或若干人,问你这些人是否构成一个小圈子,那也是一瞬间就能判断完成的事,所以,这个小圈子问题也是一个NP问题。
类似的问题还有很多,你大可上网搜索一下。那“NP问题”中的“NP”到底是什么含义?其实它的全称叫“Non-deterministic polynomial”,中文为”非确定性多项式时间”问题。这个名字起得有点奥妙,其实意思也不难。在学术上,在判定一个问题的复杂度时,都是问一个是非题,这是非题的最后一句永远是:“这个程序或算法会停机吗?”,“停机”的意思就是程序运行终止,并(对NP问题)输出一个“是”或“非”的结果。
当然 ,之前提到的所有NP问题都必然会停机的,只要你枚举所有情况。所以,我们问的会更具体点:“这个程序会在多项式时间里停机吗”?P问题显然都会在多项式时间内停机,NP问题就有意思了。
比如那个三色地图问题,如果这幅地图存在某种三种颜色的着色方案,你运气也比较好,尝试不久就找到一种合理的着色方案,那么程序就很快停机了。但如果这幅地图不存在三种颜色着色方案,那么你必须等到程序枚举了所有方案,才能等到一个否定的答案。这样程序运行时间就是成指数时间增加了。所以,你能看出“非确定性多项式时间”的含义,就是这个问题如果有解,那么你可能可以在多项式时间内停机,但这是“非确定性的”。
有人还提出一个更强力的论据,就是搞一堆计算机,并行执行程序。比如,如果这幅地图可能的着色方案有1万种,那我就用1万台电脑,分别检查这1万种不同的着色情况,那 必然在多项式时间就里给出结果了。所有的“NP问题”都有这样的特点,就是你可以靠“堆CPU”来大幅缩短计算时间,因为检查某个答案是快的。
所以人们就问,以上这种问题与多项式时间算法问题有本质区别吗?是否存在某个问题,检查它的答案很快,但不可能有一个多项式时间内的求解算法?
你可能会说,这些问题出来那么久,都没有人找到多项式时间算法,那不就说明它们会不会有多项式算法了?但是数学家都是“杠精”,没有证明就不能下结论。
另一方面“P问题是否等于NP问题”,这个问题本身也很重要。现在绝大多数人认为“P!=NP”,但如果最终证明“P问题等于NP问题”,那后果很严重。因为我们现在绝大多数加密算法,都是基于“P问题不等于NP问题”这个假设。如果P=NP,那糟糕了,意味着很多加密算法都可以有多项式时间算法破解密码,那这种加密算法也就崩溃了。另外有很多实用算法都是NP的,比如一些药物分子形状的计算、导航仪的路径规划,都与NP问题相关。这是P与NP问题的实用意义。
从理论意义上来讲,P与NP问题是有在数理逻辑领域,有关问题复杂度分类中,两种最基础和最常见的问题形态,所以人们当然想搞清楚它们之间的关系。
那P vs NP问题为什么这么难呢?如果你要证明P=NP,那么你就要证明一个问题有多项式时间的检查算法,就肯定有多项式时间的求解算法,这看来是不太可能的。
如果要证明P!=NP,那么只要找到一个NP问题,它不存在多项式时间的求解算法。数学里,这种证明“不存在…”类型的问题,一般都是用反证法。但是这个问题怎么从反证中导出矛盾还是一个很大的问题。
此外,还有人考虑“P与NP问题”可能是如同“连续统假设”一样,“无法证明”的问题,根据“P vs NP”问题与数理逻辑和图灵机的紧密联系,这种可能性是完全存在的。
最后,你会发现以上NP问题,都是在计算机课程中,被称为“指数时间复杂度”的问题,那为什么不把 “NP问题”称为“指数时间问题”呢?这个问题其实说对了一半。确实,所有NP问题都是“指数时间”问题,但与P vs NP问题类似,我们还没有找到任何一个“指数时间问题”,肯定不是“NP问题”的。也就是“NP问题是否等于指数时间问题”仍然是一个未确定的问题。
在下一期节目里,我将介绍一下复杂度分类中其他若干种主要分类,以及它们之间的关系。简单复习一下今天内容的要点:
我们用一个问题随规模增长时,其计算量的增长的幅度,来对一个问题复杂度进行度量。“多项式时间”和“指数时间”就是两种最基本的时间复杂度问题。
如果一个问题存在多项式时间的求解方法,则它就是P问题。一个问题存在多项式时间的验证方法,则它就是NP问题。
已知P问题是NP问题的子集,但不知道是否为真子集。证明“P=NP”或者“P是NP的真子集”就是克雷研究所提出悬赏的“P vs NP”问题。
NP问题都是指数时间复杂度问题,但还不确定“NP问题”是否是“指数时间问题”的真子集。

(上图:P问题是NP问题的子集)
好,今天节目到这里。因为本期节目是第三季的第一期,所以我再插播点新闻:
首先,大老李最近加入了“科学声音”组织。感谢汪诘老师的垂青,大老李现在也是有组织的人了。希望有更多的人能支持科学声音, 支持科普节目的传播。
其次,大老李也有视频节目了,请移步哔哩哔哩或海外观众上油管,并搜索“大老李聊数学”,可以搜到我的节目。目前我的视频内容主要是将音频配上图片或网页配合观众理解。因为制作视频非常费精力,所以目前暂时内容还不多。我也希望听到各位反馈,告诉我你想看到的视频内容。
最后,如果你目前还只在喜马拉雅上订阅了我第二季节目的话,请一定搜索一下“大老李聊数学第三季”或“大老李聊数学全集”,以便得到后续节目的通知。第二季的专辑我就关闭了。
今天节目到这里,下期再见!