2010年8月19日星期四

理论计算机初步:P vs NP - 问题概述

P = NP?

这个问题,作为理论计算机科学的核心问题,其声名早已经超越了这个领域。它是Clay研究所的七个百万美元大奖问题之一,在2006国际数学家大会上,它是某个1小时讲座主题

要说起P和NP是什么东西,得先从算法的多项式时间复杂度谈起,注意,这里面的两个P都是指Polynomial。

一个问题的规模指的是输入的总位数,比如一个n个数的排序问题,输入规模就是n。注意,在某些时候,输入规模是要值得注意的,比如判定一个数n是否 是一个质数这个问题,它的输入规模并不是n,而是log(n),因为一个数n用大约log(n)位就能表示出来了,这也是为何枚举因子判定素数的算法并不 是多项式时间算法的原因。

如果一个算法,它能在以输入规模为参变量的某个多项式的时间内给出答案,则称它为多项式时间算法。注意:这里的多项式时间是指算法运行的步数。一个算法是否是多项式算法,与计算模型的具体的物理实现没有关系,虽然大多数假想的计算模型不可能有任何物理的实现。

P指确定型图灵机上的具有多项式算法的问题集合,NP指非确定型图灵机上具有多项式算法的问题集合,这里N是Non-Deterministic的意思(图灵机的概念见理论计算机初步:算法和计算模型)。

脱离图灵机的概念,就在普通的计算机上看,P问题是指能够在多项式时间求解的判定问题(判定问题指只需要回答是和不是的问题),而NP问题则是指那些其肯定解能够在给定正确信息下在多项式时间内验证的判定问题。比如,要判定一个数是合数,如果给我一个约数,我们就很快判定它就是合数。所以判定一个数是合数的问题属于NP。 下面是一些NP问题的例子:

零子集和问题

给n个整数,判断是否可以从中找到若干个数,其和为0。
旅行商问题

有n个城市,一个推销员要从其中某一个城市出发,不重复地走遍所有的城市,再回到他出发的城市。问这个推销员的最短路程(是否小于指定的K)。

从上面的定义知道,NP包含P。P vs NP问题指P是否完全等于NP,即确定型图灵机和非确定图灵机的性能是否一样。

人们为何要提出NP问题?因为,大多数遇到的自然的难解问题,最后都发现它们是NP问题。如果我们能证明NP跟P的关系,则解决了无数问题的算法复杂度问题。

NP里面有无数个不同的问题,我们是否要一个一个地判定它们是否属于P呢?P vs NP问题的美妙和简洁之处便在于在NP中,有一个子类,NP完全(NP Complete,简记为NPC)问题,指的是那些NP中最难的那些问题:所有其它的NP问题都可以归约到这些NP完全问题。也就是说,只要这些NP完全问题的某一个得到解决,无论是证明其存在多项式算法,还是不存在,都意味着P vs NP问题的解决。

而几乎所有NP里面无法确定是否属于P的问题最后都被证明为NP完全。正因为如此,多数理论计算机学家都猜测P≠NP。目前已知的NP完全问题数以千计,上面引用中的例子都是完全问题,更多NP完全问题见NP完全问题的不完全列表

一个很自然的想法是如果NP≠P,则NP-P里面的问题都是完全问题。至少有两个自然的问题,一个是大数分解(给出一个数的质因数分解式),另一个 是图同构问题(给出两个图,它们是否同构),它们既没有被证明是P的,也没有被证明是NP-完全。但是更惊人的是还有这个定理:
如果NP≠P,那么NP-P中存在非NP完全问题。

当然,这种问题具体是什么样子,是无法用直观的语言表示出来,它纯粹是一个数学上的构造性证明。

假如P=NP,世界将会怎样?

在计算机复杂度理论中,P问题指的是能够在多项式的时间里得到解决的问题,NP问题指的是能够在多项式的时间里验证一个解是否正确的问题。 虽然人们大多相信P问题不等于NP问题,但人们目前既不能证明它,也不能推翻它。P是否等于NP是计算机科学领域中最突出的问题,在千禧年七大难题中排在 首位。科学家们普遍认为P≠NP是有原因的。让我们来看一看,如果哪一天科学家证明了P=NP,寻找一个解和验证一个解变得同样容易,那这个世界将会变得 怎样?
已知的NPC难题将全部获解,这将瞬间给各个科学领域都带来革命性的进展。整数规划、01规划、背包问题全部获解,运筹学将登上一个全新的高度; 数据库的串行化、多处理器调度等问题也随之解决,大大提高了计算机的性能。同时,空当接龙、扫雷、数独等经典游戏也由于获得了多项式的算法而在很大程度上 失去了意义。
算法研究方向将发生全面转移。对算法的研究可能会转向围棋等NP-Hard问题。算法设计的学问与“NP问题统一解”的关系正如小学应用题与列方程解题的关系一样,将成为一种纯粹锻炼思维的游戏。

一些新型的自动编程语言将出现,并将逐渐取代传统的编程语言。这种新型编程语言扮演着一个“判定性/最优化问题万能解决器”的角色。在新的 编程语言中,你只需要用代码指明输入数据与输出数据的关系,而无需关心计算输出数据的步骤。只要这种关系是多项式时间内可计算的,编译器将自动找到解法。 在新型编程语言的支持下,人们唯一需要考虑的是,如何把实际问题转化成数学模型。
利用Occam剃刀原理,困扰人类已久的自然语言处理问题将被一举攻破。只要提供足够多的语言文字材料,计算机将很快掌握这门语言,并反过来为语 言学提供新的科学体系。考虑这样一个最优化问题:输入一大批语句样本,它们有的符合语法,有的不符合语法;寻找一个最简单的算法,将这些语句输入这个算法 时,算法能正确得出它是否符合语法。显然,这个问题本身是NP的(当然前提是该算法是多项式的),因此计算机可以在多项式时间内找到能判定语法正误的最简 算法。我们有理由相信,这个算法也就是人类头脑中正在使用的算法,因此它能够适用于所给材料之外的其它语句,并具有自我学习的功能。分词技术、手写识别、 语音朗读、语音识别等难题在一瞬间全部攻破。
很可能计算机给出的自然语言处理算法完全不同于传统语言学的那一套方法,因此传统语言学本身将受到极大的冲击。字、词、句的概念很可能被重新界定,词类、句式的概念有可能被完全颠覆。

类似地,所有人工智能问题都将得到解决。我们只需要向计算机提交足够多的情境以及与之对应的正常人反应,计算机就可以找出一种能正确生成出 这些反应的最简算法,并且由我们的Occam剃刀假设,这种算法能够适用于更广的范围,完全模仿人类的行为。在网络上,再没有任何办法能够把计算机和人区 别开来。验证码将变得毫无意义。
计算机不仅能轻易通过图灵测试,还能精确地模仿某一个特定的人。如果你能把某个人的网络聊天记录全部搜集起来,把这个人和网友们的对话全部递交给计算机,计算机将会很快学会如何模仿这个人。网络的身份鉴定将变得相当困难,很可能不得不借助一些物理方式。

数学证明可以完全交给计算机来处理。寻找一个反例和验证一个反例变得同样简单,一切错误的猜想都将瞬间被推翻。事实上,寻找一个数学证明和 验证一个证明的正确性也变得同样简单,因此一切正确的命题也能够瞬间找到一个最简的证明。困扰人类数个世纪的数学猜想将逐一获解。数学领域内部将掀起一次 革命,数学研究真正成为了一门“提出问题的艺术”而不再是“解决问题的艺术”。数理逻辑等底层研究,以及开创数学新分支并将其形式化,将成为数学研究的主 流方向。
类似地,一切具有解释性并可以形式化的科学都可以借助计算机寻求现象的最佳解释方案。物理学、化学、经济学、心理学等学科都将会受到不同程度的影响。

md5算法不再有效,判定一个串的md5是否等于给定值与寻找一个md5等于给定值的串一样轻松。RSA算法也不再有效,寻找一个质因子和 判断整除性也变得一样简单。事实上,发明任何新的密码算法都是徒劳——计算机可以根据一大批明文密文样本推算出生成密文的算法(只要这个算法是多项式 的)。现有的密码学体系彻底崩溃。理论上不具有可预测性的一次一密协议成为唯一安全的密码协议。但人们很快注意到,密码本本身的生成也不能依赖于任何伪随 机数算法,必须完全借助于物理算法。从这个角度来说,纯机器的密码协议将不复存在,任何身份验证手续都必须借助物理手段。互联网可能会变得非常不可靠。