P/NP问题
 |
| 千禧年大奖难题 |
|---|
P/NP问题是理论计算机科学中计算复杂度理论领域至今未解决的问题，是克雷数学研究所七题千禧年大奖难题之一。P/NP问题包括复杂度类P与NP的关系。1971年由史提芬·古克（Stephen A. Cook）和列昂尼德·列文分别提出。
P=NP
[编辑]复杂度类P即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有可以在多项式时间内验证它的解是否正确的决定问题组成，或者等效的说，那些可以在非确定型图灵机上在多项式时间内找出解的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的：
- P和NP相等
在2002年对于100研究者的调查中，61人相信答案是否定的，9人相信答案是肯定的，22人不确定，而8人相信问题可能和现在所接受的公理独立，所以不可能证明或证否。[1]对于正确的解答，有一个一百万美元的奖励。
NP-完全问题（或者叫NPC）的集合在这讨论有重大作用，它们可以大致的描述为那些在NP中最不像在P中的（确切定义细节请参看NP-完全理论）。计算机科学家现在相信P、NP和NPC类之间的关系如图中所示，其中P和NPC类不相交。
简单来说，P=NP即：“若问题的答案可以很快验证，其答案是否也可以很快被计算出来。”
例如某大数是否合数：如53308290611有否非平凡因数。答案是肯定的，虽然人手找出一个因数很麻烦。从另一个方面讲，如果有人声称答案是“对，224737可以整除53308290611”，则我们可以很快用除法验证。验证一个数是除数比找出一个明显除数来简单得多。用于验证一个正面答案所需的信息也称为证明。所以我们的结论是，给定正确的证明，问题的正面答案可以很快（也就是，在多项式时间内）验证，而这就是这个问题属于NP的原因。
虽然这个特定的问题，最近也获证实在P类中（参看下面的关于"质数在P中"的参考），这一点也不明显，而且有很多类似的问题相信不属于类P。
像上面这样，把问题限制到“是／不是”问题并没有改变原问题（即没有降低难度）；即使我们允许更复杂的答案，最后的问题（是否FP=FNP）是等价的。
学术定义
[编辑]更正式一些，一个决定问题是一个取一些字符串为输入并要求输出为是或否的问题。若有一个算法（譬如图灵机，或一个LISP或Pascal的程序并有无限的内存）能够在最多nk步内对一个串长度为n的输入给出正确答案，其中k是某个不依赖于输入串的常数，则我们称该问题可以在多项式时间内解决，并且将它置入类P。直观的讲，我们将P中的问题视为可以较快解决的问题。
现在假设有一个算法A(w,C)取两个参数，一个串w，也就是我们的决定问题的输入串，而另一个串C是“建议证明”，并且使得A在最多nk步内产生“是／否”答案（其中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棋盘上）是NP困难的。因为可以证明P≠EXPTIME（指数时间），这些问题位于P之外，所以需要比多项式时间更多的时间。判定皮尔斯伯格算术中的命题是否为真的问题更加困难。Fischer和Rabin于1974年证明每个决定Presburger命题的真伪性的算法有最少22cn的运行时间，c为某个常数。这里，n是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如停机问题，而它们无法在任何给定时间内解决。
P真的容易处理吗？
[编辑]上面所有的讨论，假设了P表示“容易”而“不在P中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点：
- 它忽略了常数因子。一个需要101000n时间的问题是属于P的（它是线性时间的），但是事实上完全无法处理。一个需要10-100002n时间的问题不是在P中的（它是指数时间的），但是对于n取值直到几千时还是很容易处理的。
- 它忽略了指数的大小。一个时间复杂度n1000属于P，但是很难对付。已经证明在P中存在需要任意大的指数的问题（参看时间层次定理）。一个时间复杂度2n/1000的问题不属于P，但对于n直到几千还是容易应对的。
- 它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间n中解决，但是很偶尔你会看到需要时间2n的特例。这问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于P。
- 它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于P，虽然事实上它可以很快求解。这实际上是解决属于NP而还不知道是否属于P的问题的一个办法（参看RP，BPP）。
- 新的诸如量子计算机这样的计算模型，可能可以快速的解决一些尚未知道是否属于P的问题；但是，没有一个它们已知能够解决的问题是NP完全的。不过，必须注意到P和NP问题的定义是采用像图灵机这样的经典计算模型的术语表述的。所以，即使一个量子计算机算法获发现能有效解决一个NP完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类P和NP相等的证明。
P≠NP的观点
[编辑]多数计算机科学家[谁？]相信P≠NP[2]。该信念的一个关键原因是经过数十年对这些问题的研究，没人能发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法（Karp的21个NP完全问题，在最早发现的一批中，有所有著名的已经存在的问题）。进一步，P=NP这样的结果会导致很多惊人结果，那些结果现在被相信不成立，如NP=反NP和P=PH。
也有这样论证：问题难求解（P）但易验证（NP），这和我们日常经验相符。
从另一方面讲，某些研究者认为我们过于相信P≠NP，而应该也去寻找P=NP的证明。例如，2002年有这声明：[3]
| “ | 倾向P≠NP的主要论据是在穷举搜索领域完全没有本质性进展。也就是说，以我的观点，这是一个很弱的论据。算法的空间非常大，而我们只是在开始探索的起点。……费马最后定理的解决也显示非常简单的问题可能只有用非常深刻的理论才能解决。 | ” |
| ——Moshe Y. Vardi，莱斯大学 | ||
| “ | 过分依赖某种投机的猜测不是规划研究的一个好导引。我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。 | ” |
| ——Anil Nerode，康奈尔大学 | ||
关于证明的难度的结果
[编辑]虽然百万美元的奖金和投入巨大却没有实质性结果的大量研究足以显示该问题很难，但是还有一些形式化的结果证明为什么该问题可能很难解决。
最常引用的结果之一是设计神谕。假想你有部魔法机器可以解决单一问题，例如“判定某数是否质数”，这魔法机器可以瞬间解决这问题。我们的新问题是，若我们获允许任意利用这机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P=NP和P≠NP二者都可以证明。这个结论带来的后果是，任何可以通过修改神谕来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。
如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P=NP问题。[1]（页面存档备份，存于互联网档案馆）这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类定理得到证明，该定理的可能证明方法有越来越多的陷阱要规避。
这实际上也是为什么NP完全问题有用的原因－若对于NP完全问题存在有一个多项式时间算法，或者没有这样的算法，这将能用一种相信不被上述结果排除在外的方法来解决P=NP问题。
多项式时间算法
[编辑]没人知道多项式时间算法对于NP完全问题是否存在。但是如果这样的算法存在，我们已经知道其中的一些了！例如下面的算法正确地接受了一个NP完全语言，但是没人知道通常它需要多久执行。它是一个多项式时间算法当且仅当P=NP。
// 接受NP完全语言的一个算法子集和。
//
// 这是一个多项式时间算法当且仅当P=NP。
//
// “多项式时间”表示它在多项式时间内返回“是”，若
// 结果是“是”，否则永远运行。
//
// 输入：S = 一个自然数的有限集
// 输出："是"如果某个S的子集加起来等于0。
// 否则，它永远运行没有输出。
// 注意: "程序数P"是你将一个整数P写为二进制，然后
// 将位串考虑为一个程序。
// 每个可能的程序都可以这样产生，
// 虽然多数什么也不做因为有语法错误。
//
FOR N = 1...infinity
FOR P = 1...N
以S为输入运行程序数P N步
IF程序输出一个不同的整数的列表
AND所有整数都在S中
AND整数的和为0
THEN
OUTPUT "是"并 停机
若P=NP，则这是一个接受一个NP完全语言的多项式时间算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。
可能我们想要“解决”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？没有人知道。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句：
IF程序输出一个完整的数学证明
AND证明的每一步合法
AND结论是S确实有（或者没有）一个和为0的子集
THEN
OUTPUT "是"（如果获证实，就"不是"）并停机
逻辑表述
[编辑]P=NP问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用一阶逻辑加上最小不动点操作（实际上，这允许了递归函数的定义）来表达。类似，NP是可以用存在性二阶逻辑来表达—也就是，在关系、函数、和子集上排除了全称量词的二阶逻辑。多项式等级，PH中的语言对应与所有的二阶逻辑。这样，“P是NP的真子集吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”
花絮
[编辑]普林斯顿大学计算机系楼将二进制代码表述的“P=NP？”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。[4] [5]
康奈尔大学的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：[6]
反证法。设P=NP。令y为一个P=NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真，但因为P=NP，该证明y可在多项式时间内由这样的科学家发现，但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。
注释
[编辑]- ^ Wayback Machine（网页存档）. web.archive.org. 2005-04-04 [2017-09-05]. （原始内容存档于2005-04-04）.
- ^ P≠NP - 百度学术. xueshu.baidu.com. [2024-05-12]. （原始内容存档于2024-05-12）.
- ^ William I. Gasarch. The P=?NP poll. (PDF). SIGACT News. June 2002, 33 (2): 34–47 [29 December 2008]. doi:10.1145/1052796.1052804. （原始内容存档 (PDF)于2019-10-27）.
- ^ https://www.cs.princeton.edu/general/images/csbricksjpg. [2018-10-04]. （原始内容存档于2019-02-17）. 外部链接存在于
|title=(帮助) - ^ https://www.cs.princeton.edu/general/bricks. [2018-10-04]. （原始内容存档于2017-12-14）. 外部链接存在于
|title=(帮助) - ^ http://www.cs.cornell.edu/hubes/pnp.htm. [2005-07-15]. （原始内容存档于2005-09-27）. 外部链接存在于
|title=(帮助)
参考文献
[编辑]- 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.
延伸阅读
[编辑]- Fraenkel, A. S.; Lichtenstein, D. Computing a Perfect Strategy for n*n Chess Requires Time Exponential in N.. Lecture Notes in Computer Science. 1981: 278–293. doi:10.1007/3-540-10843-2_23. （原始内容存档于2017-04-25）.
- Garey, Michael; Johnson, David. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman and Company. 1979. ISBN 0-7167-1045-5.
- Goldreich, Oded. P, Np, and Np-Completeness. Cambridge: Cambridge University Press. 2010. ISBN 978-0-521-12254-2. Online drafts（页面存档备份，存于互联网档案馆）
- Immerman, N. Languages which capture complexity classes. SIAM Journal on Computing. 1987, 16 (4): 760–778 [2018-01-19]. doi:10.1137/0216051. （原始内容存档于2013-04-29）.
- Cormen, Thomas. Introduction to Algorithms. Cambridge: MIT Press. 2001. ISBN 0-262-03293-7.
- Papadimitriou, Christos. Computational Complexity. Boston: Addison-Wesley. 1994. ISBN 0-201-53082-1.
- Fortnow, L. The Status of the P versus NP problem. Communications of the ACM. 2009, 52 (9): 78 [2018-01-19]. doi:10.1145/1562164.1562186. （原始内容存档于2017-02-15）.
- Fortnow, L.; Gasarch, W. Computational complexity. [2019-04-27]. （原始内容存档于2009-05-01）.
外部链接
[编辑]- 未来数学家的挑战（P与NP的简介，清楚明了）（页面存档备份，存于互联网档案馆）（繁体中文）
- The Clay Math Institute Millennium Prize Problems
- 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（页面存档备份，存于互联网档案馆）
