|
独立思考是突破颜值文化的唯一出路 古哥古点 2015年11月30日 《P和NP》 一个有名的台湾人说过一句话“我是不是我的我”，这句话说起来有点绕嘴，但是英语里有更拗口的句子: That that is, is that that is not, 'is not.' Is that it? It is. 实际上，这句话只要改变标点的位置至少可以读出四种完全不同的意思。另外的三种是： That that is, is. That that is not, is not. Is that it?It is. That that is, is that that is. Not is not. Is that it? Itis. That that is, is that that is not. Is not 'is that' it? It is. 这是一种致歧文字序列组合，通过不同的断句法可以由相同的一组字符或单词产生出多种含义，在各种语言里都存在这样的现象。今天我们要说的不是文字游戏，而是要从一个数学概念的歧义性理解错误引出本期话题。上一期节目曾经介绍了克雷数学研究（ClayMathematics Institute）颁布的七道千禧大奖难题（Millennium Prize Problems）并详细解释了其中的Navier-Stokes方程。本期接着来讲里面的另外一个极具挑战性的题目：“Pversus NP”，或者更流行的叫法是“P=NP”问题。这里面NP就是一个容易被人理解错误的名称。至于它是如何被误解的，稍后再说。 千禧年大奖难题是七个由美国克雷数学研究所于2000年5月24日公布的数学难题，解题总奖金700万美元。根据克雷数学研究所制定的规则，这一系列挑战不限时间，题解必须发表在国际知名的出版物上，并经过各方验证，只要通过两年验证期和专家小组审核，每解破一题可获奖金100万美元。七道题目分别是： P/NP问题霍奇猜想、庞加莱猜想（已证明）、黎曼猜想、杨-米尔斯存在性与质量间隙、纳维-斯托克斯存在性与光滑性、贝赫和斯维讷通-戴尔猜想。 [Source: slideplayer.com] 先从一个简单的问题说起。拼图游戏大家一定都玩过，小孩玩的初级拼图一般不过几十块，随着级别越高，拼图的块数也就越多，而复原所需的时间自然就越长。人们大概都有这种感觉，从200块拼图增加到400块，耗用的时间却不止2倍，而是明显要长出很多。这种感觉是正确的，因为如果把拼图问题转换成计算模型，它的求解困难程度的确是随着拼图块数的增加呈现出非线性增长。 一个计算问题的复杂程度该怎么去衡量呢？这其实是个挺伤脑子的定义问题，我们可以看看下面几个例子： 1. 把一组数列当中的最大一个数字挑出来。 2. 给出一组整数，判断其中有没有若干个数加在一起的和刚好为0。 3. 给出n个城市和城市间的道路里程，让一个人从A城市出发，不重复的走遍所有城市并回到A。在所有的可能路径中，总路程最短是多少。 4. 给出一个整数，找出其全部因子。 美国城市行走的旅行商问题（Traveling Salesman Problem） 动态计算演示程序可以查看： 这四个问题分别是最大值查找、零和子集（Subset Problem）、旅行商（Traveling SalesmanProblem）和大数分解问题。你觉得哪一个更复杂呢？问题的形态千差万别，它们的难度是一样的吗？似乎很难有个主观的判断，那客观的度量该如何建立呢？是用计算这些问题的耗时来衡量吗？当然不对，计算耗时有赖于计算机的性能，显然不够公平。所以，人们一般使用运算的总次数来表征某个计算方法的复杂度。但这里面仍然有一个问题。计算一道题目所进行的运算可能有很多种类型，比如说减加乘除、移位、逻辑运算等。假设有两个题目，一个需要计算100次乘法和10次加法，另一个需要运算10次乘法和100次加法。看起来运算总次数是一样的，都是110，但由于乘法的时间开销远大于加法，所以完全可以忽略加法而只考虑乘法作为基本运算。基本运算就是能有效度量某个算法计算量的运算单位。在更一般的情形下，这个单位可以是人们定义出的若干计算步骤的组合，该组合会在算法中不断的被执行，从而成为算法计算规模的度量单元。研究者并不关心单次基本运算的耗时长短，这并不反映复杂度。真正关键的是要考察在求解一个问题时，计算量随问题规模的扩大而表现出的增长趋势，这才是算法复杂度的本质。 增长趋势可以分为如下几种情形。如果问题的规模扩大n倍（可以类比为拼图游戏的块数增加n倍，块数代表了问题规模），求解计算量也随之增加n倍，这种增长就是线性增长，记为O（n）。如果问题的规模扩大n倍，运算次数扩大n的平方倍、立方倍、四次方倍等等，这种增长就叫做幂级增长，记为O（n^k），k就是增长幂次。如果问题的规模扩大n倍，计算量增长的速度比幂级数还要快，比如指数级或阶乘级攀升，这就称为指数增长或超指数增长。一般说来，衡量一个算法的优劣并不是看它在处理小规模问题上的表现，而是看它在问题规模增大时计算总量的膨胀程度。计算负荷增长速率越慢说明算法性能越好。这就像拼图问题一样。如果拼图总数只有四块或八块，问题的规模很小，即使不用任何的拼图技巧，上来随便抓两块就开始尝试，这种硬凑方法也是可以很快给出答案的，但这不能说明硬凑是个好算法。因为从计算角度来说，硬凑就是一种暴力搜索法（BruteForce）。暴力搜索在拼图规模变大时会带来计算负担的指数级暴增从而让求解变得越发不可能。对于拼图问题来说，暴力搜索法的运算复杂度甚至达到了O（4ⁿ×n！），真是令人恐怖的高。 拼图问题直接搜索的计算复杂度为O（4ⁿ×n！） [Source: wpbusinesstips.com] 在算法复杂度的分级中，低于或等于幂级增长速度的被称为多项式算法。一个问题如果具有多项式算法的解就被称为P（Polynomial）问题，意思是求解该问题的计算时间可以用一个关于问题规模n的多项式来表示（例如n就是拼图问题中的块数）。如果实在看不懂这种解释，也没关系，就直接把多项式问题理解为一种容易计算的简单问题就好。 有简单就有复杂。有P就有NP。既然P代表着有多项式算法（Polynomial）的简单问题，那很自然的，NP就应该代表没有多项式解法（NonPolynomial）的复杂问题，也就是比较难算的问题。我们常常会听到有程序员说“这个题目是NP的，没有其他好办法了，我只能暴力了！”或者说“NP的，硬搜吧！”。这些说法的潜台词就是，面对着有指数或超指数级复杂度的所谓NP问题，算法设计上没有更好的选择而只能用穷举搜索来应对，因为NP问题不存在简单的多项式解法。可就是在这儿，这些程序员出现了节目一开头所说的理解歧义。NP并不是非多项式（NonPolynomial）的意思，而是非确定的多项式（Non-deterministic Polynomial）。“非”要否定的不是“多项式”而是“确定性”，“多项式”一词是跟在后面的，所以NP仍然是在指一种多项式方法，而不是很多人错误理解中的非多项式算法。可是，这个前缀“非确定”指的又是什么呢？它又怎么会引导人们联想到“非多项式”的含义上去呢？ 图灵机模型 [Source: wikipedia] 学计算机的人都知道图灵机模型：一条无限长纸带，一个读写头，可记录有限状态的纸带格子，也就是记忆单元，就构成了图灵机。在任何一个时刻，图灵机将会停留在纸带的某个单元处读写其中的状态信息并根据指令把机器置于有限状态集合当中的一种。人们目前使用的计算机采用的都是这个模型。然而这只是图灵机里最简单的一种模型，叫做“确定式图灵机”，也就是一个单元只能记录一个物理状态的机器。如果一个单元可以同时对应多个状态，这就构成了强大的“非确定式图灵机”。显然，非确定式图灵机只能停留在想象中，在物理上还无法实现状态的并行。量子计算机有某些类似于非确定式图灵机的特点，但它不是真正的非确定式图灵机，尽管如此，量子计算还是拥有着强大到难以想象的应用潜力。非确定式图灵机的多状态特性让其处理能力完全压倒了确定式图灵机。如果一个很困难的计算问题放在非确定式图灵机上，是可能获得多项式时间解法的，这时该问题就被称为“非确定的多项式问题”，也即所谓的NP问题。可见NP原本的意思是指在牛叉机器上的多项式算法，这个定义要基于无法实现的非确定式图灵机。那么很自然的，人们就会关心这类问题和能实现的确定式图灵机之间会有什么关系。研究者们很快发现，NP问题如果移植到普通图灵机上执行，它将等价于这样一种问题。这些问题是否可以被确定式图灵机快速求解并不能确定，但是如果给出了某个猜想的解，则一定可以在多项式时间内验证解的正确性。这样的问题非常多，还以拼图游戏为例，拼图的复原是极其困难的，但检验某个复原方案是不是正确却非常简单，在极短的时间内就可以完成，所以拼图游戏就是一个NP问题。而从此之后，NP问题的定义就转变为可以在多项式时间内被图灵机验证的问题。P问题要求多项式时间内可求解，NP问题只要求多项式时间内可验证，自然两者就分别成了简单问题和困难问题的代名词。又由于在实践中，困难问题的算法往往都是指数以上级别的增长率，所以人们就习惯性的把NP这个名号安在了非多项式问题的头上，谬误由此产生。 确定式图灵机与非确定式图灵机比较 [Source: Amazon S3] 接下来一个很重要的问题出现了。多项式时间内可解一定意味着多项式时间内可验，解都给出来了，当然也就被验证了！这就是说一个P问题一定是NP的。这很好理解，一个简单问题当然可以看做一个简化形式的复杂问题。但反过来的结论成立吗？一个NP问题一定也同时是个P问题吗？从可验证性能得出可求解性吗？换种表达方式来说，P问题是包含于NP问题的子集，但这个子集合是NP的真子集吗？全体NP问题里面除了P问题子集外，还存不存在另外的部分，这一部分里的问题都是非多项式复杂度的（不是P）。如果确实存在这样一个超出P的部分，那至少应该能找到一个不是多项式复杂度的NP问题的例子。找到了这样的例子，就足以说明NP集合比P集合大，NP≠P。反之，两者就是一回事儿，NP=P。NP和P究竟相不相等，现在仍然不清楚，这就是七大千禧大奖难题之一的“Pversus NP”问题至今未解的局面。 凭直觉多数人会觉得NP≠P，NP的范围应该比P大！因为找出一个不能在多项式时间内求解，但是可以在多项式时间内被验证的例子似乎很容易！最开始说的拼图游戏不就是吗？它可以迅速的被验证，但其暴力搜索的复杂度却达到了O（4ⁿ×n！），这当然不是多项式算法了，那不就证明了NP里有比P更难的问题吗？可是千禧大奖难题要这么简单，还能给它设立百万奖金吗？“P=NP”这个证明题目的古怪刁钻之处就在这里。虽然包括专家在内的大多数人都相信NP集合里含有比P问题更难的其他问题，可是这样的例子就是找不到。问题出在哪里呢？拼图游戏的穷举搜索法固然是非多项式的，但你怎么知道拼图问题就不存在着其他的巧妙解法，而这个解法是多项式算法呢？只要无法排除这种可能性，就不能断言一个问题一定不是P复杂度的，也就不能确定在NP里面存在着非P的例子。正因为要排查一个问题所有的可能解法是极其困难的，因此在这儿出现了一个有趣的现象，尽管一般说来，构造反例的反向证明要比正向证明来的简单，但是在P=NP这个问题上，人们反而在研究初期没太关注于找寻反例，而是把精力更多的集中在正向工作上。因为说到底，NP这个集合到底是在含有P的同时还有富余的空间，还是像紧身衣一样把P无缝的包裹着以至于就等同于P，这个问题搞不清的深层次原因还在于人们对NP集合的内部结构认知不深，没有描绘出所有NP问题在难度分布上的台阶。 人们猜测中的NP集合、P集合的相对关系 [Source: youtube] 摸索算法难度台阶的研究在接下来的时间里取得了令人惊讶的进展，以至于人们如今每每回顾这个成果还是不由得惊叹数学之美。数学家们虽然暂时没有弄清P和NP的关系，但却在NP集合里找到了一个极为古怪神奇的子集，称为“NP-完全”问题（NP-Complete），简称NPC。为了说明“NP-完全”问题是什么，先来看两个方程的求解。一次方程“3x+4=10”，相信每个人都会解。一个减法，一个除法，结果就出来了。二次方程“2x²+4x-9=23”也不难解，用求根公式就行。但下面的问题是，解一次方程的时候能不能套用二次方程的求根公式？当然可以，把一次方程看做是二次项系数为0的特殊二次方程即可。一个简单的NP问题A如果可以在多项式时间内被变形成另一个NP问题B，而B的解法也适用于A，我们就说A被“约化”（Reducibility）成了B。刚才的例子中，一次方程就被约化成了二次方程，以此类推二次方程还可以被约化为三次、四次方程等。可以看出，每一次约化都是在提升了问题的复杂度的同时扩展了问题的代表面，二次方程比一次方程难，但却覆盖了更多的方程个体，所以约化就是一种深度配合广度的升级工具。这种升级有什么用呢？非常有用，这恰好体现出数学家的聪明。他们的思路是这样的。如果NP问题里确有比P更难的问题存在，那说明NP集合里存在着多个难度台阶，P台阶当然算一个，在非P区域里面，难度或许还有更多的起伏层次。要确认NP集合的这种垂直结构，必须创造出一种可对NP集合进行难度排序的工具，“约化”就是这种工具。找到某一个具体的NP问题A作为种子，从种子A出发，向上一路“约化”提升，逐次得到更难的A1、A2、A3...等一系列NP问题，每一个排序靠后问题的解一定适用于前面，从而形成难度的向前覆盖。基于难度配合广度的规则，约化在让NP问题的难度走高的同时也一定加大了其覆盖面。数学家们很感兴趣的是，这种提升进行到最后会发生什么？难度的提高有没有尽头，如果有所谓的最难水平，当约化进行到这个最难NP问题A*时，它的覆盖范围会是怎样的。A*的解向下通吃的NP问题一定构成了NP的一个子集，那有没有可能从其他的种子问题B开始，也通过B的约化序列得到它的最难问题B*覆盖的另一个NP子集。以此类推，是不是还有C*、D*等等子集。这些子集之间是什么关系，用这种方式是不是可以把NP集合划分成若干区块，而各区域的难度最高峰是不等的。 这是一个令人激动的研究构想，可得到的结果是谁都没想到的，A*最后的覆盖范围居然是整个NP集合，这就是说A*的解可以适用于全体NP问题。这是一个不得了的发现，它等于宣告了一个A*问题可以代表整个NP。如果是别的种子B经过约化得到最难的B*，它和A*之间是可以互相约化的。A*的解适用于B*，B*的解也适用于A*，故此NP集合里的最难问题不止一个而是一群，从形式上来说可能千差万别，但它们全都是相等难度的。在这个最高难度台阶里的NP问题就叫做“NP-完全”问题，“NP-完全”问题的解一定向下兼容所有的NP问题。所以在数学上，NPC的的正式定义就是要满足两个条件：一，它本身是一个NP问题；二，全体NP问题都可以约化为它。 预期中的NP集合、P集合、NP-完全问题集合、NP-难问题集合的相对关系。这里的图示默认NP不等于P。 [Source: Quora] 至今为止人们已经找到了数千个NPC问题，可谓琳琅满目。现在要想证实某个新问题是NPC，非常简单，只要能证明该问题可以在多项式时间内约化为这数千个已知NPC中的任何一个即可。但是第一个NPC问题是怎么得来的呢？它可没办法和别的NPC建立约化关系，因为它之前没有先例！第一个“NP-完全”问题来自1971年美国数学家斯蒂芬·库克（StephenArthur Cook）在经典论文“复杂度理论的证明途径”（The complexity of theorem proving procedures）中提出的SAT问题。在当时，库克没有想到那么多，他的研究是基于NP问题的基础定义开展的，就是在一台可以多状态并行的非确定式图灵机上去计算。正是因为有了这种抽象性，他才得以创造出可代表全体NP问题的首个“NP-完全”问题。具体的证明过程非常复杂，我们说一种简单的但不准确的理解方法。一个最重要的观察点是，任何一个计算问题都可以转换成一系列真假判断的组合。还以拼图问题来说明，你可以先随便挑出第一块，之后随机拿出第二块进行尝试拼接，尝试的过程就是不断的去判断某一个块是否拼在了正确的位置。如果是，保留；如果不是，进行下一次的判断，直到全部拼图完整为止。这就是暴力搜索法转换成真假判断序列的说明，而其实任何的计算方法都可以做类似转换。有了这样的认识，再利用抽象的图灵机状态表、字符表等定义，全体NP问题就可以转换成统一的逻辑运算形式。库克证明了在多状态的非确定式图灵机上，这些判断都可以组合成一个复杂的“布尔逻辑可满足性”问题（SAT，Booleansatisfiability problem）。什么是SAT呢？一大堆的逻辑变量通过“与或非”等逻辑运算的连接可以组合成一个逻辑表达式，表达式最终为真还是为假取决于各个逻辑变量的取值。如果在所有的变量取值可能性中，有至少一种情况让表达式最后为真，就称该表达式被满足。计算某一个逻辑表达式能不能有被满足的可能性，这个问题就叫做SAT问题，库克证明SAT可以在多项式时间内被非确定式图灵机解决，所以SAT本身是NP问题，又由于其他NP问题都可以转换成SAT，故此它就成了第一个被找到的“NP-完全”问题。 “NP-完全”问题的发现意义重大，它相当于全体NP问题的人大代表，每一个“NP-完全”问题的解必然可以在多项式时间内解出其他的NP问题。所以只要能在数千个已知的NPC中，找到一个例子是有多项式复杂度解法的，那全体NP就都是P级复杂度的，P=NP。反过来，只要证实有一个NPC没有任何的多项式解法，那P≠NP。“NP-完全”问题有点像药物开发中的标靶，它提供了“Pversus NP”研究里的数千个最佳靶点。这里还要顺便介绍一下另一个经常被提起的概念，叫做“NP-难”问题（NP-hard）。“NP-完全”问题的定义是由两个条件组成的：第一条，本身得是一个NP问题，第二条解对其他NP问题都兼容。如果去掉这一条只要求第二条，这样的问题就叫“NP-难”问题。为什么要用“难”这个字眼呢？就是因为它比“NP-完全”问题更复杂，它少了一条限制，从而有更大的自由度，可以不必在多项式时间内可验证。 研究者建立的复杂度世界地图,即各种复杂度集合之间相互关系。最外层的EXPSPACE是一个包含了可以在O(2^p(n))空间内解决的决定性问题的集合。 [Source: Technology] NPC的出现一度为破解“P versus NP”难题带来了曙光，可是时至今日，人们依然毫无所获。所取得的进展，不过是沿着这种思路，在不同的划分工具下，又定义出了许多种不同的复杂度集合，它们的范围有的比P大，有的比NP小，有的部分重合于NP，有的在NP的外围，其总数已经接近500个，在这里我们就不一一细说了。为什么有了这些认知积累，而最关键的P与NP之间的难度关系还是没有理清呢？“约化”手段在我们刚才的介绍中被描述为一种可以区分难度层次的工具，实际上，这个描述不准确，“约化”只是保证了后面问题的解适用于前面。严格地讲，这只能说明后面问题的难度不会低于前面，但不能说更难，因为“难”的定义依然要回到运算复杂度的区别上。约化在运算复杂度上没有提供更多的信息，通俗的说，它只是提供了一种感觉上的高度区分，这种感觉深度还不能对应于算法复杂性深度，所以P=NP问题至今无解。 讲到这里，我相信有很多的朋友也许还是缺乏直观的感觉，一个问题在短时间内可验证和在短时间内可求解到底是什么关系？对于这个区别，想想密码的破解就很好理解了。黑客攻击一个防护系统时，往往是多次输入密码进行尝试，这就是用验证来求解的最好例子。尝试输入的密码可以在极短的时间内验证正确性，所以这是一个NP问题。在正常情况下，暴力破解的运算量是指数级别的，该解法不是多项式算法，这种非多项式特性提供了密码保护的安全性。可问题是，非多项式特性是始终存在的还是仅仅对暴力破解算法成立？数字密码破解这个NP问题真的可以被确定不存在P级算法吗？谁能保证没有其他的高级理论或模型让黑客可以仅仅通过多项式级别的尝试就打开防护大门呢？其实很难证明，这就可以帮助我们理解为什么P=NP至今悬而未决。但反过来说，既然连银行这种事关千家万户金钱的系统都敢于放心的把安全性置于NP≠P的假设基础之上，坚定地认为数字密码的复杂度一定是超过P级的，我们就可以知道人们对NP≠P的信心有多么强。2002年，有人组织了100位相关研究领域的专家就“Pversus NP”这一课题的最后结局进行了问卷调查，结果61个人相信NP≠P，9个人相信NP=P，22个人不确定，还有8个人认为这道题目可能出的有问题以至于无法证明。这8个人的思路真的是很别致，这就是为什么我们看投票时总是特别关注那些少数票的原因。 各个复杂度集合的计算膨胀速率 [Source: rsif.royalsocietypublishing.org/content/14/128/20160990] 或许是“P versus NP”问题困扰人们太久了，康奈尔大学的胡勃·陈（Hubert Chen）博士给出了一段无厘头式证明。其中使用的是反证法： 如果P=NP， 其证明方法y应该可以被一位专家在多项式时间内验证，对此能力我们完全确信。 既然可以用多项式时间验证，证明本身就应该是一个NP问题。 根据P=NP， 证明本身也就是一个P问题， 所以证明y应该在多项式时间内被发现。 在我们这一代人当中，y至今仍未出现， 所以这和前面矛盾。 故此NP≠P。 世界上最美的问题就是这样，看起来那么简单，但解起来又那么遥远。俗语讲：这山望着那山高，这是在刺讽心无定见。可是P和NP的问题告诉我们，能看出来谁高就不错了，最让人没注意的是“远近高低各不同”。有人开玩笑的说，P问题不复杂，NP问题也不复杂，NP=P的论证才是真正的复杂。但无论如何，最后的结果最好还是NP≠P，否则世界就要一片大乱，我们现在使用的所有密码都会变成一张脆弱的簿纸，因为那里面最重要的一道题目，把一个超大整数进行因数分解就会变得非常简单。幸运的是，现在看来情况还没有那么糟，因为大整数分解仍是一个不知道是不是“NP-完全”问题的“NP-难”问题。
|
|
|
