热点 数学

P vs. NP:从一则数学家谋杀案说起

严酷的魔王 发表于  2013-12-04 11:47

美剧《基本演绎法》(也就是美版“福尔摩斯”)第 2 季第 2 集中,两位研究 NP 问题的数学家被谋杀了,凶手是同行,因为被害者即将证明“P=NP 问题”,她为独吞成果而下了毒手。然而凶手的动机,并不是千禧年大奖难题那100万美元的奖金——解决了 P=NP 问题,就能够破译世界上所有的密码系统,这里面的利益比100万美元多多了。

剧中只用了一句话来介绍 P=NP 的意义:“能用电脑快速验证一个解的问题,也能够用电脑快速地求出解”。这句过于简单的话可能让大家一头雾水,今天我们就来讲一讲 P vs. NP。

什么是P和NP?

《基本演绎法》S02E02 截图。

计算机科学的一个主要研究方向是提高各种算法的速度。尤其在当前火热的“大数据”概念下,算法速度更显重要。很容易理解,处理的数据越大,计算的耗时就越多。对于一个算法,人们能够分析出运算时间与数据量之间的大致函数关系,这个关系被称为时间复杂度,它定量描述了该算法的运行时间。

假设有 n 个数要排序。一个初级的冒泡排序算法所需时间可能与 n2 成正比,快一点的算法所需时间与 nlog(n) 成正比。在某些条件下,桶排序算法所需时间甚至只和 n 成正比。最不实用的算法就是输入的数字随机排列,直到出现完全有序的情况为止……记前三个算法的时间复杂度分别记为 O(n2)、O(nlogn) 和 O(n),最后的“猴子排序”(Bogosort)算法平均时间复杂度则达到了 O(n*n!)。

在上面的例子中,前三种算法的复杂度是 n 的多项式函数;最后一种算法的复杂度是 n 的阶乘,根据斯特林公式,n! 相当于指数级别的增长。当 n 特别小时,多项式级的算法已经快过指数级的算法。当 n 非常大时,人类根本看不到指数级复杂度算法结束的那天。自然的,大家会对多项式级别的算法抱有好感,希望对每一个问题都能找到多项式级别的算法。问题是——每个问题都能找到想要的多项式级别的算法吗?

在一个由问题构成的集合中,如果每个问题都存在多项式级复杂度的算法,这个集合就是 P 类问题(Polynomial)。这意味着,即使面对大规模数据,人们也能相对容易地得到一个解,比如将一组数排序。

“NP”的全称为“Nondeterministic Polynomial”,而不是“Non-Polynomial”。NP 类问题指的是,能在多项式时间内检验一个解是否正确的问题。比如我的机器上存有一个密码文件,于是就能在多项式时间内验证另一个字符串文件是否等于这个密码,所以“破译密码”是一个 NP 类问题。NP 类问题也等价为能在多项式时间内猜出一个解的问题。这里的“猜”指的是如果有解,那每次都能在很多种可能的选择中运气极佳地选择正确的一步。

不妨举个例子:给出 n 个城市和两两之间的距离,求找到一个行走方案,使得到达每个城市一次的总路程最短。我们可以这样来“猜测”它的解:先求一个总路程不超过 100 的方案,假设我们可以依靠极好的运气“猜出”一个行走路线,使得总长度确实不超过 100,那么我们只需要每次猜一条路一共猜 n 次。接下来我们再找总长度不超过 50 的方案,找不到就将阈值提高到75…… 假设最后找到了总长度为 90 的方案,而找不到总长度小于 90 的方案。我们最终便在多项式时间内“猜”到了这个旅行商问题的解是一个长度为 90 的路线。它是一个 NP 类的问题。

也就是说,NP 问题能在多项式时间内“解决”,只不过需要好运气。显然,P 类问题肯定属于 NP 类问题。所谓“P=NP”,就是问——是不是所有的 NP 问题,都能找到多项式时间的确定性算法?

P会不会等于NP?

《基本演绎法》S02E02 截图。

这个问题目前还没有定论,当下学术界的大多数意见是 P≠NP。一个主要原因是,这么多年过去了,人们仍然没有找到解决上千个 NPC 问题中任何一个的多项式复杂度的算法。等等,NPC 又是什么?

在与数不尽的问题搏斗的过程中,人们有时候会发现,解决问题 A 的算法可以同时用来解决问题 B。例如问题 A 是对学生的姓名与所属班级同时排序,问题 B 是对人们按照姓名做排序。这时候,我们只需要让班级全都相同,便能照搬问题 A 的算法来解决问题 B。这种情况下,数学家就说,问题 B 能归约为问题 A。

人们发现,不同的 NP 问题之间也会出现可归约的关系,甚至存在这么一类(不只是一个)问题,使得任何其它的 NP 问题都能归约到它们上。也就是说,能够解决它们的算法就能够解决所有其它的 NP 问题。这一类问题就是 NPC 问题。这样的问题人们已经找到了几千个,如果我们给其中任何一个找到了多项式级别的算法,就相当于证明了 P=NP。但是人们至今没有成功找到,所以大家对 P=NP 的信心大打折扣。

解密无遮拦?

《基本演绎法》S02E02 截图。

虽然前景很不乐观,但是不妨来假想一下,如果 P=NP,《基本演绎法》中所说的“破解密码只是小菜一碟”就会成真了吗?

前面说过,证明 P=NP 的一个主要方法就是,给某一个 NPC 问题找到一个快速算法。但是,也不排除有人给出一个“存在性”而非“构造性”的证明,只是告诉大家存在符合要求的算法,但没法详细描述出来。如果 P=NP 被人以这种方式证明出来了,我们也没法依葫芦画瓢地把这个神奇的算法在电脑上写出来,所以对破解密码仍然没有帮助。

退一步说,假如有人构造出可以运用的多项式算法,以此证明了这个问题。这个算法恐怕也很复杂(毕竟这么难找),它的多项式级别的复杂度也可能会非常慢。假设这个算法的复杂度达到了 O(n10),那我们依然面临着不小的麻烦。即使 n=100,运算时间也会增长到非常巨大的地步。

再退一步,假设人类的运气好到 P=NP 是真的,并且找到了复杂度不超过 O(n3) 的算法。如果到了这一步,我们就会有一个算法,能够很快算出某个帐号的密码。《基本演绎法》里面所想象的可能就要成真了,所有的加密系统都会失去效果——应该说,所有会把密码变成数字信息的系统都会失去效果,因为这个数字串很容易被“金钥匙”计算出来。

除此之外,我们需要担心或期许的事情还有很多:

  • 一大批耳熟能详的游戏,如扫雷、俄罗斯方块、超级玛丽等,人们将为它们编写出高效的AI,使得电脑玩游戏的水平无人能及。
  • 整数规划、旅行商问题等许多运筹学中的难题会被高效地解决,这个方向的研究将提升到前所未有的高度。
  • 蛋白质的折叠问题也是一个 NPC 问题,新的算法无疑是生物与医学界的一个福音。

Wikipedia上有一个关于NPC问题的列表。如果我们手握解决NPC问题的金钥匙,它们全都能被飞快地解决。

除此之外,P=NP 最令人震撼的成果之一可能是下面这段话:

……(P=NP)会将数学转变为让计算机对任何问题寻找拥有合理长度的证明的学科,因为我们能够在多项式时间内验证一个证明是否正确。这些问题也正好包括千禧年大奖的那些问题。

它出自 NP 完全理论奠基人史提芬·古克的笔下。上面这些只言片语的描述,已经展现出了 P=NP情况下,世界将会出现怎样一副天翻地覆的变化。也正是因为这样的结果实在难以置信,人们普遍倾向于相信 P≠NP。我也希望 P≠NP ,这样至少我的网银相对来说还是挺安全的。

 

参考文献

  1. P vs. NP on Elementary
  2. 什么是P问题、NP问题和NPC问题
  3. A personal view of average-case complexity
  4. P versus NP problem

相关的果壳网小组

热门评论

  • 2013-12-04 14:40 uncrea

    看完突然想到,如果一个问题真的解真的会立即带来如此之大的社会改变,假使有人真的得到解他还会公布吗?

    [12] 评论
  • 2013-12-04 13:59 毛骡 金属材料学博士
    引用文章内容:等等,NPC 又是什么?

    NPC难道不是非玩家角色吗?

    [3] 评论

显示所有评论

全部评论(50)
  • 1楼
    2013-12-04 11:52 忧伤的尼姑

    终于出现本专业严肃内容了。激动的杀了~~~

    来自NOKIA Lumia 620
    [1] 评论
  • 2楼
    2013-12-04 11:57 木容

    好贴杀

    [0] 评论
  • 3楼
    2013-12-04 11:57 忧伤的尼姑

    其实pvnp也就那个规约比较酷,别的都还好

    来自NOKIA Lumia 620
    [0] 评论
  • 4楼
    2013-12-04 13:23 引力波

    杀杀杀,先杀后看

    [0] 评论
  • 5楼
    2013-12-04 13:59 毛骡 金属材料学博士
    引用文章内容:等等,NPC 又是什么?

    NPC难道不是非玩家角色吗?

    [3] 评论
  • 6楼
    2013-12-04 14:15 冰火梦幻

    Nondeterministic Polynomial
    怎么看这个都是说”不能在多项式时间验证“……

    [0] 评论
  • 7楼
    2013-12-04 14:40 uncrea

    看完突然想到,如果一个问题真的解真的会立即带来如此之大的社会改变,假使有人真的得到解他还会公布吗?

    [12] 评论
  • 8楼
    2013-12-04 14:52 吴师傅 数学专业

    @ 飘飘37

    [0] 评论
  • 9楼
    2013-12-04 14:54 hetaoljt

    倒数第二段,P=(!=?)NP本身也是千禧年大奖之一吧……

    [0] 评论
  • 10楼
    2013-12-04 16:12 星夜听雨

    现在写文章不计算一下复杂度再用优化方法优化一下都不好意思投。

    [0] 评论
  • 11楼
    2013-12-04 16:15 MirrorJewel
    引用@uncrea 的话:看完突然想到,如果一个问题真的解真的会立即带来如此之大的社会改变,假使有人真的得到解他还会公布吗?


    所以剧里面的情节就是:凶手解决了此问题却秘而不宣,暗地里借自己写出的程序破密码牟利,然后当她发现另两个同行也即将解决此问题时为了保证自己的利益就把他们干掉了……

    [0] 评论
  • 12楼
    2013-12-04 16:54 BoleynSu
    引用@冰火梦幻 的话:Nondeterministic Polynomial怎么看这个都是说”不能在多项式时间验证“……

    不是”不能在多项式时间验证“而是”能在多项式时间验证“。
    它的本意是在非确定性图灵机上的P类问题,可以证明这两个说法等价。
    这篇文章其实也不是十分严谨,有些硬伤,不过作为科普应该是够了。

    [0] 评论
  • 13楼
    2013-12-04 19:20 吴师傅 数学专业
    引用@hetaoljt 的话:倒数第二段,P=(!=?)NP本身也是千禧年大奖之一吧……

    是。

    [0] 评论
  • 14楼
    2013-12-04 20:56 冰火梦幻
    引用@BoleynSu 的话:不是”不能在多项式时间验证“而是”能在多项式时间验证“。它的本意是在非确定性图灵机上的P类问题,可以证明这两个说法等价。这篇文章其实也不是十分严谨,有些硬伤,不过作为科普应该是够了。

    非确定性(图灵机上的)P问题,原来是这个意思。

    [0] 评论
  • 15楼
    2013-12-04 23:46 St_Satan
    引用@毛骡 的话:NPC难道不是非玩家角色吗?

    是全国人民代表大会的意思╮(╯_╰)╭
    好罢差不多一个意思╭(╯^╰)╮

    [2] 评论
  • 16楼
    2013-12-05 10:07 井底之蛙_52710

    这篇文章对np的解释完全是瞎扯淡。

    [0] 评论
  • 17楼
    2013-12-05 10:48 IVV万岁
    引用@井底之蛙_52710 的话:这篇文章对np的解释完全是瞎扯淡。

    哦,还好我完全看不懂。瞎扯淡的天书和天书对我没区别。

    [0] 评论
  • 18楼
    2013-12-05 13:46 东门黄狗

    的确,终于见到计算理论方面的文章了,欣慰..

    [0] 评论
  • 19楼
    2013-12-06 03:55 基友-你的肥皂掉了

    N=NP 也不会对密码造成太大安全隐患吧。因为密码是 id和密码的配对,要是什么都没有硬猜的话,还是取决于服务器的接收速度,因为id和密码没有必然联系。当然如果截取到hash值的话可能会猜的快些。

    来自果壳精选

    [0] 评论
  • 20楼
    2013-12-06 03:56 基友-你的肥皂掉了

    不过如果证明P=NP,真是翻天覆地的变革。

    来自果壳精选

    [0] 评论
  • 21楼
    2013-12-06 12:56 leeonfish

    这么多年终于理解这问题了……

    [0] 评论
  • 22楼
    2013-12-06 13:23 spacewander

    证明解的存在远远不等于能够构造可行解……

    [1] 评论
  • 23楼
    2013-12-06 13:36 alecksun
    引用@基友-你的肥皂掉了 的话:=NP 也不会对密码造成太大安全隐患吧。因为密码是 id和密码的配对,要是什么都没有硬猜的话,还是取决于服务器的接收速度,因为id和密码没有必然联系。当然如果截取到hash值的话可能会猜的快些。...


    你说的那个叫口令(Password),不是密码(Cryptography)。打个比方,晚上进曹操军营要喊一声“鸡肋”。这叫口令,用处是识别身份。打仗的时候呼叫友军:“长江长江我是黄河”,这叫 密码。用处是隐藏信息。文中所说的针对的是密码而不是口令。

    [0] 评论
  • 24楼
    2013-12-06 16:19 Kanagi_Miss
    引用@井底之蛙_52710 的话:这篇文章对np的解释完全是瞎扯淡。

    那请您来解释一下~

    [0] 评论
  • 25楼
    2013-12-06 19:10 oAsIs____

    作为高数不合格过的数学渣,看不懂也完全无压力的说

    [0] 评论
  • 26楼
    2013-12-07 07:33 怪盗14_12

    不明觉厉

    来自果壳精选

    [0] 评论
  • 27楼
    2013-12-09 08:47 morphine1021
    引用@井底之蛙_52710 的话:这篇文章对np的解释完全是瞎扯淡。

    定义是对的啊,NP problem有两个等价的定义:答案可以被deterministic turing machine在P时间内验证,或者是nondeterministic turing machine也就是有无限多线程的理想机器在P时间内解出。

    [0] 评论
  • 28楼
    2013-12-09 08:55 morphine1021
    引用@基友-你的肥皂掉了 的话:=NP 也不会对密码造成太大安全隐患吧。因为密码是 id和密码的配对,要是什么都没有硬猜的话,还是取决于服务器的接收速度,因为id和密码没有必然联系。当然如果截取到hash值的话可能会猜的快些。...

    感觉主要问题是任何被hard-problem based技术加密的数据包都可以在P时间内被解密...基于https session的交易信息形同虚设。

    [0] 评论
  • 29楼
    2013-12-09 14:49 稻叶下的智子

    计算原理这门课要挂了TAT

    [0] 评论
  • 30楼
    2013-12-10 18:12 ReinhardWang

    我想吐槽的是,竞争对手根本不用大开杀戒,A数学家的论文一定会被交给同领域的B科学家(凶手)审稿……然后………………

    [0] 评论

显示所有评论

你的评论

登录 发表评论

严酷的魔王
严酷的魔王 统计学专业本科生,数学控

作者的其他文章

更多科研事,扫码早知道

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 免责声明 联系我们 移动版 移动应用

©2017果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:13488674940