作者: 张志强

, 发表于 2006-08-23

, 共 1787 字 , 共阅读 195 次

系列：理论计算机初步

查看该系列所有文章

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.