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

作者: , 共 1787 字
系列:理论计算机初步

查看该系列所有文章

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.

系列: 理论计算机初步 »
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
类似文章:
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
前面已经提到了显示中大多数难解问题问题最后都被证明是 NP-完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在这篇文章提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本On the graph isomorphism problem
相似度: 0.134
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是Andrew Yao的研究方向
本科时有同学扫雷最快可以在 60 多秒完成高级难度,让我这种最快 130 秒的人非常惭愧,当时就想着编一个全自动的扫雷程序,不过一直也没写。今天才知道,原来扫雷问题是NP 完全的...
注: 这个问题来自China Theory Week 2008的 Open Problems Session。
PS: PCP 可以说是理论计算机领域近 20 年来的最重要的结果之一,它给了NP 问题一个新的刻画,并且提供了一种证明近似算法下界的方法。下面是 yijia 写的 PCP 介绍。
上篇文章已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP-完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。