P/NP问题

导入

P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”(Clay Mathematics Institute, 简称CMI)在千禧年大奖难题中收录。P/NP问题中包含了复杂度类 P与NP的关系。1971年史提芬·古克和 Leonid Levin 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的（P=NP?）。

P 和NP

复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内可解决的问题；类NP有所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的:

P和NP相等吗?

在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。[1] 对于正确的解答，有一个$1,000,000美元的奖励。

NP-完全问题(或者叫NPC)的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在NP中最不像在P中的。(确切定义细节请参看NP-完全)理论计算机科学家现在相信P, NP,和NPC类之间的关系如图中所示，其中P和NPC类不交。

本质上，P = NP问题问道：如果是/不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。给定一个大数Y,我们可以问Y是否是复合数。例如，我们可能问53308290611是否有非平凡的因子。回答是肯定的，虽然手工找出一个因子很麻烦。从另一个方面讲，如果有人声称答案是"对，因为224737可以整除53308290611",则我们可以很快用一个除法来验证。验证一个数是除数比首先找出除数来简单得多。用于验证一个正面答案所需的信息也称为证书。所以我们的结论是，给定正确的证书，问题的正面答案可以很快的(也就是，在多项式时间内)验证，而这就是这个问题属于NP的原因。虽然这个特定的问题，最近被证明为也在P类中(参看下面的关于"质数在P中"的参考),这一点也不明显，而且有很多类似的问题相信不属于类P。

限制到是/不是问题并没有改变问题；即使我们允许更复杂的答案，最后的问题(是否FP = FNP)是等价的。

形式化定义

更正式一些，一个决定问题是一个取一些字符串为输入并要求输出为是或否的问题。若有一个算法（譬如图灵机，或一个LISP或Pascal的程序并有无限的内存）能够在最多n^k步内对一个串长度为n的输入给出正确答案，其中k是某个不依赖于输入串的常数，则我们称该问题可以在多项式时间内解决，并且将它置入类P。直观的讲，我们将P中的问题视为可以较快解决的问题。

现在假设有一个算法A(w,C)取两个参数，一个串w，也就是我们的决定问题的输入串，而另一个串C是“建议证明”，并且使得A在最多n^k步之内产生“是/否”答案（其中n是w的长度而k不依赖于w）。进一步假设

w是一个答案为“是”的例子，当且仅当，存在C使得A(w,C)返回“是”。

则我们称这个问题可以在非决定性多项式时间内解决，且将它放入NP类。我们把算法A作为一个所建议的证明的检验器，它运行足够快。（注意缩写NP代表“Non-deterministic（非确定性）Polynomial（多项式）”而不是代表“Non-Polynomial（非多项式）。）

NP完全

要解决P = NP问题，NP完全的概念非常有用。不严格的讲，NP完全问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如，旅行商问题的判定问题版本是NP完全的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题的一个特例。所以若旅行商问题被证明为在P内，则P = NP！旅行商问题是很多这样的NP完全的问题之一。若任何NP完全的问题在P内，则可以推出P = NP。不幸的是，很多重要的问题被证明为NP完全，但没有一个有已知快速的算法。

更难的问题

虽然是否P=NP还是未知的，在P之外的问题是已经知道存在的。寻找国际象棋或围棋（在n乘n棋盘上）是指数时间完全的。因为可以证明P ≠ EXPTIME（指数时间），这些问题位于P之外，所以需要比多项式时间更多的时间。判定Presburger算术中的命题是否为真的问题更加困难。Fischer和Rabin于1974年证明每个决定Presburger命题的真伪性的算法有最少2^(2^(cn))的运行时间，c为某个常数。这里，n是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如停机问题。它们无法在任何给定时间内解决。

P真的容易处理吗？

上面所有的讨论假设了P表示“容易”而“不在P中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点：

它忽略了常数因子。一个需要10¹⁰⁰⁰n时间的问题是属于P的（它是线性时间的），但是事实上完全无法处理。一个需要10^-100002ⁿ时间的问题不是在P中的（它是指数时间的），但是对于n 取值直到几千时还是很容易处理的。
它忽略了指数的大小。一个时间复杂度n¹⁰⁰⁰属于P，但是很难对付。已经证明在P中存在需要任意大的指数的问题（参看时间等级定理）。一个时间复杂度2^n/1000的问题不属于P，但对与n直到几千还是容易应对的。
它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间n中解决，但是很偶尔你会看到需要时间2ⁿ的特例。这个问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于P。
它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于P，虽然事实上它可以很快求解。这实际上是解决属于NP而还不知道是否属于P的问题的一个办法（参看RP， BPP）。
新的诸如量子计算机这样的计算模型，可能可以快速的解决一些尚未知道是否属于P的问题；但是，没有一个它们已知能够解决的问题是NP完全的。不过，必须注意到P和NP问题的定义是采用象图灵机这样的经典计算模型的属于表述的。所以，即使一个量子计算机算法被发现能够有效的解决一个NP完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类P和NP相等的证明。

计算机科学家为什么认为P ≠ NP？

多数计算机科学家相信P≠NP。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了（Karp的21个NP完全问题，在最早发现的一批中，有所有著名的已经存在的问题]]）。进一步地，P = NP这样的结果会导出很多惊人的结果，那些结果现在被相信是不成立的，例如NP = 余NP和P = PH。

也有这样论证的：问题较难求解(NP)但容易验证(P)，这和我们日常经验是相符的。

参看

外部链接及参考

The Clay Math Institute Millennium Prize Problems
Gerhard J. Woeginger. The P-versus-NP page. Lists a number of incorrect solutions to the problem.
A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A 31 (1981) 199-214.
E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000.
Neil Immerman. Languages Which Capture Complexity Classes. 15th ACM STOC Symposium, pp.347-354. 1983.
Computational Complexity of Games and Puzzles
Manindra Agarwal, Nitin Saxena, Neeraj Kayal, "PRIMES is in P", Preprint, August 6, 2002
The "PRIMES is in P" FAQ
Scott Aaronson's Complexity Zoo