理论计算机初步: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问题的例子:

1.零子集和问题

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

2.旅行商问题

有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完全问题。

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

参阅

备注:中国大陆可以通过http://browseatwork1.com 访问wikipedia.

Q.E.D.


上一篇:理论计算机初步:前言2006年8月15日
这段时间Blog的更新频率大大降低,因为发现没啥好写的,也没有写文章的欲望。前段时间提到了我加入中国赛客联盟,而且给的说明语是"算机|数学|算

下一篇:理论计算机初步:P vs NP - 历史,现状和未来2006年8月24日
上篇文章已经提到,P vs NP是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。