跳转到内容

P/NP问题：修订间差异

本页使用了标题或全文手工转换
维基百科，自由的百科全书
以互动方式浏览历史
←上一版本
删除的内容 添加的内容
可视化wikitext
Sidazhang（留言 | 贡献）
85次编辑
无编辑摘要
add unsolved on en
 
（未显示超过100个用户的173个中间版本）
第1行： 第1行：
{{noteTA
|G1 = IT
}}
{{多個問題|
{{expert|subject=计算机科学|time=2012-07-28}}
{{Cleanup rewrite||翻译质量不佳，语调或风格不适合[[Wikipedia:更优秀条目写作指南#寫作風格|百科全书的写作方式]]，读起来亦像[[Wikipedia:维基百科不是什么#維基百科不是發表創新意念的地方|评论]]。|time=2022-11-27T03:56:00+00:00}}
{{Disputed|time=2022-11-27T03:56:00+00:00}}
|update=2022-5-18
}}
{{unsolved|計算機科學|如果一个问题的解可以快速检验正确性，那么这个问题一定可以快速求解吗？}}
{{千禧年难题}}
{{千禧年难题}}


'''{{lang|en|P/NP}}问题'''是[[理论计算机科学]]中[[计算复杂度理论]]领域至今未解决的问题，是[[克雷数学研究所]]七題[[千禧年大奖难题]]之一。P/NP问题包括[[复杂度类]][[P (复杂度)|P]]与[[NP (复杂度)|NP]]的关系。1971年由[[史提芬·古克]]（Stephen A. Cook）和{{tsl|en|Leonid Levin|列昂尼德·列文}}分別提出。
<!--Das P/NP-Problem ist ein offenes Problem der theoretischen Informatik, speziell der Komplexitätstheorie und wurde vom Clay Mathematics Institute in die Liste der Millennium-Probleme aufgenommen. Es beinhaltet die Beziehung zwischen den Komplexitätsklassen P und NP. 1971 stellten Stephen Cook und Leonid Levin unabhängig voneinander erstmals die Frage, ob diese beiden Komplexitätsklassen identisch sind-->
'''P/NP问题'''是在[[理论信息学]]中[[计算复杂度理论]]领域里至今没有解决的问题，它被“[[克雷数学研究所]]”（Clay Mathematics Institute, 简称CMI）在[[千禧年大奖难题]]中收录。P/NP问题中包含了[[复杂度类]][[P]]与[[NP]]的关系。1971年[[史提芬·古克]](Stephen A. Cook) 和 [[Leonid Levin]] 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的（P=NP?）。


== P 和NP ==
== P=NP ==<!--
<!--Die Komplexitätsklasse P beinhaltet alle Probleme, welche von deterministischen Turingmaschinen in polynomiell beschränkter Zeit gelöst werden können. Dagegen beinhaltet NP die Menge aller von nichtdeterministischen Turingmaschinen in polynomialzeit lösbaren Probleme. Aus diesen beiden Definitionen geht hervor, dass P eine Teilmenge von NP ist, unklar ist aber, ob NP ebenfalls eine Teilmenge von P ist und die beiden Klassen somit identisch wären.-->
Die Komplexitätsklasse P beinhaltet alle Probleme, welche von deterministischen Turingmaschinen in polynomiell beschränkter Zeit gelöst werden können. Dagegen beinhaltet NP die Menge aller von nichtdeterministischen Turingmaschinen in polynomialzeit lösbaren Probleme. Aus diesen beiden Definitionen geht hervor, dass P eine Teilmenge von NP ist, unklar ist aber, ob NP ebenfalls eine Teilmenge von P ist und die beiden Klassen somit identisch wären.-->
复杂度类'''[[P (复杂度类)|P]]'''包含所有那些可以由一个[[图灵机|确定型图灵机]]在多项式表达的时间内解决的问题；类'''[[NP (复杂度)|NP]]'''由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在[[非确定图灵机]]上在[[多项式时间]]内找出的问题的集合。很可能，[[计算理论]]最大的未解决问题就是关于这两类的关系的:
复杂度类'''[[P (复杂度)|P]]'''即為所有可以由一个[[图灵机|确定型图灵机]]在[[多项式]]表达的时间内解决的问题；类'''[[NP (复杂度)|NP]]'''由所有可以在多项式时间内验证它的解是否正確的决定问题组成，或者等效的说，那些可以在[[非確定型圖靈機]]上在[[多项式时间]]内找出解的问题的集合。很可能，[[计算理论]]最大的未解决问题就是关于这两类的关系的：
:'''P'''和'''NP'''相等吗?
:'''P'''和'''NP'''相等
在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。[http://www.cs.umd.edu/~gasarch/papers/poll.ps] 对于正确的解答，有一个[[Clay Mathematics Institute|$1,000,000美元的奖励]]。
在2002年对于100研究者的调查中，61人相信答案是否定的，9人相信答案是肯定的，22人不确定，而8人相信问题可能和现在所接受的公理独立，所以不可能证明或证否。<ref>{{cite web |title=Wayback Machine（网页存档） |url=http://www.cs.umd.edu/~gasarch/papers/poll.ps |website=web.archive.org |date=2005-04-04 |access-date=2017-09-05 |archive-date=2005-04-04 |archive-url=https://web.archive.org/web/20050404002304/http://www.cs.umd.edu/~gasarch/papers/poll.ps |dead-url=yes }}</ref>对于正确的解答，有一个[[克雷數學研究所|一百萬美元的奖励]]。


[[NP-完全]]问题(或者叫'''NPC''')的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在'''NP'''中最不像在'''P'''中的。(确切定义细节请参看[[NP-完全]])理论[[计算机科学家]]现在相信'''P''', '''NP''',和'''NPC'''类之间的关系如图中所示，其中'''P'''和'''NPC'''类不交。[[Image:Complexity classes.png|thumb|250px|假设'''P''' &ne; '''NP'''的复杂度类的图解.如'''P''' = '''NP'''则三个类相同.]]
[[NP-完全]]问题（或者叫'''NPC'''）的集合在这讨论有重大作用，它们可以大致的描述为那些在'''NP'''中最不像在'''P'''中的（确切定义细节请参看[[NP-完全]]理论）。[[计算机科学家]]现在相信'''P'''、'''NP'''和'''NPC'''类之间的关系如图中所示，其中'''P'''和'''NPC'''类不相交。
[[File:Complexity classes.svg|thumb|250px|假设'''P'''≠'''NP'''的复杂度类的图解。如'''P'''='''NP'''则三个类相同。]]


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


例如某大数是否[[合数]]：如53308290611有否非平凡[[因數]]。答案是肯定的，虽然人手找出一个因數很麻烦。从另一个方面讲，如果有人声称答案是「对，224737可以整除53308290611」，则我们可以很快用除法验证。验证一个数是除数比找出一個明顯除数来简单得多。用於验证一个正面答案所需的信息也称为'''[[证明]]'''。所以我们的结论是，给定正确的证明，问题的正面答案可以很快（也就是，在多项式时间内）验证，而这就是这个问题属于'''NP'''的原因。
限制到是/不是问题并没有改变问题；即使我们允许更复杂的答案，最后的问题(是否[[FP (复杂度)|FP]] = [[FNP (复杂度)|FNP]])是等价的。


虽然这个特定的问题，最近也獲证實在'''P'''类中（参看[[#外部链接和参考|下面的]]关于"质数在P中"的参考），这一点也不明显，而且有很多类似的问题相信不属于类'''P'''。
==形式化定义==


像上面这样，把问题限制到“是／不是”问题并没有改变原问题（即没有降低难度）；即使我们允许更复杂的答案，最后的问题（是否[[FP (复杂度)|FP]]=[[FNP (复杂度)|FNP]]）是等价的。
更正式一些，一个''决定问题''是一个取一些[[字符串]]为输入并要求输出为是或否的问题。若有一个[[算法]]（譬如[[图灵机]]，或一个[[Lisp编程语言|LISP]]或[[Pascal编程语言|Pascal]]的程序并有无限的内存）能够在最多''n''<sup>''k''</sup>步内对一个串长度为''n''的输入给出正确答案，其中''k''是某个不依赖于输入串的常数，则我们称该问题可以在''多项式时间''内解决，并且将它置入类'''P'''。直观的讲，我们将'''P'''中的问题视为可以较快解决的问题。


== 学术定义 ==
现在假设有一个算法A(''w'',''C'')取两个参数，一个串''w''，也就是我们的决定问题的输入串，而另一个串''C''是“建议证明”，并且使得A在最多''n''<sup>''k''</sup>步之内产生“是/否”答案（其中''n''是''w''的长度而''k''不依赖于''w''）。进一步假设
: ''w''是一个答案为“是”的例子，当且仅当，存在''C''使得A(''w'',''C'')返回“是”。
则我们称这个问题可以在''非决定性多项式时间''内解决，且将它放入'''NP'''类。我们把算法A作为一个所建议的证明的检验器，它运行足够快。（注意缩写'''NP'''代表“'''N'''on-deterministic（非确定性）'''P'''olynomial（多项式）”而''不是''代表“'''N'''on-'''P'''olynomial（非多项式）。）


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


现在假设有一个算法A('''w''','''C''')取两个参数，一个串'''w'''，也就是我们的决定问题的输入串，而另一个串'''C'''是“建议证明”，并且使得A在最多'''n'''<sup>'''k'''</sup>步内产生“是／否”答案（其中'''n'''是'''w'''的长度而'''k'''不依赖于'''w'''）。然後假设：'''w'''是一个答案为“是”的例子，当且仅当，存在'''C'''使得A('''w''','''C''')返回“是”。
要解决'''P''' = '''NP'''问题，[[NP完全|'''NP'''完全]]的概念非常有用。不严格的讲，'''NP'''完全问题是'''NP'''类中“最难”的问题，也就是说它们是最可能不属于'''P'''类的。这是因为''任何'''''NP'''中的问题可以在多项式时间内变换成为任何特定'''NP'''完全问题的一个特例。例如，[[旅行商问题]]的判定问题版本是'''NP'''完全的。所以'''NP'''中的''任何''问题的''任何''特例可以在多项式时间内机械地转换成旅行商问题的一个特例。
则我们称这个问题可以在'''非决定性多项式时间'''内解决，且将它放入'''NP'''类。我们把算法A作为一个所建议的证明的检验器，它运行足够快。（注意缩写'''NP'''代表“'''N'''on-deterministic（非确定性）'''P'''olynomial（多项式）”而不是代表“'''N'''on-'''P'''olynomial（非多项式）。）
所以若旅行商问题被证明为在'''P'''内，则'''P ''' = '''NP'''！旅行商问题是很多这样的'''NP'''完全的问题之一。若任何一个'''NP'''完全的问题在'''P'''内，则可以推出'''P''' = '''NP'''。不幸的是，很多重要的问题被证明为'''NP'''完全，但没有一个有已知快速的算法。


==更难的问题==
== NP完全 ==


要解决'''P'''='''NP'''问题，[[NP完全|'''NP'''完全]]的概念非常有用。不严格的讲，'''NP'''完全问题是'''NP'''类中“最难”的问题，也就是说它们是最可能不属于'''P'''类的。这是因为'''任何NP'''中的问题可以在多项式时间内变换成为任何特定'''NP'''完全问题的一个特例。例如，[[旅行推销员问题]]的判定问题版本为'''NP'''完全。所以'''NP'''中的'''任何'''问题的'''任何'''特例可以在多项式时间内转换成旅行商问题的一个特例。所以若旅行商问题能证實在'''P'''内，则'''P'''='''NP'''。旅行商问题是很多这样的'''NP'''完全的问题之一。若任何一个'''NP'''完全的问题在'''P'''内，则可以推出'''P'''='''NP'''。不幸的是，虽然很多重要的问题被证實为'''NP'''完全，但却没有一个有已知快速的算法。
虽然是否'''P'''='''NP'''还是未知的，在'''P'''之外的问题是已经知道存在的。寻找[[国际象棋]]或[[围棋]]最佳走法（在''n''乘''n''棋盘上）是[[指数时间完全]]的。因为可以证明P &ne; EXPTIME（指数时间），这些问题位于'''P'''之外，所以需要比多项式时间更多的时间。判定[[Presburger算术]]中的命题是否为真的问题更加困难。Fischer和[[Michael O. Rabin|Rabin]]于[[1974年]]证明每个决定Presburger命题的真伪性的算法有最少2^(2^(''cn''))的运行时间，''c''为某个常数。这里，''n''是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如[[停机问题]]。它们无法在任何给定时间内解决。


==P真的容易处理吗？==
== 更难的问题 ==


虽然是否'''P'''='''NP'''还是未知的，在'''P'''之外的问题是已经知道存在的。寻找[[国际象棋]]或[[围棋]]最佳走法（在''n''乘''n''棋盘上）是[[NP困难]]的。因为可以证明P≠EXPTIME（指数时间），这些问题位于'''P'''之外，所以需要比多项式时间更多的时间。判定{{tsl|en|Presburger arithmetic|皮尔斯伯格算术}}中的命题是否为真的问题更加困难。Fischer和{{tsl|en|Michael O. Rabin|Rabin}}于1974年证明每个决定Presburger命题的真伪性的算法有最少2<sup>2<sup>cn</sup></sup>的运行时间，''c''为某个常数。这裡，''n''是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如[[停机问题]]，而它们无法在任何给定时间内解决。
上面所有的讨论假设了'''P'''表示“容易”而“不在'''P'''中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点：
*它忽略了常数因子。一个需要10<sup>1000</sup>''n''时间的问题是属于'''P'''的（它是线性时间的），但是事实上完全无法处理。一个需要10<sup>-10000</sup>2<sup>''n''</sup>时间的问题不是在'''P'''中的（它是指数时间的），但是对于''n'' 取值直到几千时还是很容易处理的。
*它忽略了指数的大小。一个时间复杂度''n''<sup>1000</sup>属于'''P'''，但是很难对付。已经证明在'''P'''中存在需要任意大的指数的问题（参看[[时间等级定理]]）。一个时间复杂度2<sup>''n''/1000</sup>的问题不属于'''P'''，但对与''n''直到几千还是容易应对的。
*它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间''n''中解决，但是很偶尔你会看到需要时间2<sup>''n''</sup>的特例。这个问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于'''P'''。
*它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于'''P'''，虽然事实上它可以很快求解。这实际上是解决属于'''NP'''而还不知道是否属于'''P'''的问题的一个办法（参看'''[[RP (复杂度)|RP]]'''， '''[[BPP]]'''）。
*新的诸如[[量子计算机]]这样的计算模型，可能可以快速的解决一些尚未知道是否属于'''P'''的问题；但是，没有一个它们已知能够解决的问题是'''NP'''完全的。不过，必须注意到'''P'''和'''NP'''问题的''定义''是采用象图灵机这样的经典计算模型的属于表述的。所以，即使一个量子计算机算法被发现能够有效的解决一个'''NP'''完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类'''P'''和'''NP'''相等的证明。


== P真的容易处理吗？ ==
==计算机科学家为什么认为P &ne; NP？==
上面所有的讨论，假设了'''P'''表示“容易”而“不在'''P'''中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点：
* 它忽略了常数因子。一个需要10<sup>1000</sup>''n''时间的问题是属于'''P'''的（它是线性时间的），但是事实上完全无法处理。一个需要10<sup>-10000</sup>2<sup>''n''</sup>时间的问题不是在'''P'''中的（它是指数时间的），但是对于''n''取值直到几千时还是很容易处理的。
* 它忽略了指数的大小。一个时间复杂度''n''<sup>1000</sup>属于'''P'''，但是很难对付。已经证明在'''P'''中存在需要任意大的指数的问题（参看[[时间层次定理]]）。一个时间复杂度2<sup>''n''/1000</sup>的问题不属于'''P'''，但对于''n''直到几千还是容易应对的。
* 它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间''n''中解决，但是很偶尔你会看到需要时间2<sup>''n''</sup>的特例。这问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于'''P'''。
* 它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于'''P'''，虽然事实上它可以很快求解。这实际上是解决属于'''NP'''而还不知道是否属于'''P'''的问题的一个办法（参看'''[[RP (复杂度)|RP]]'''，'''[[BPP_(複雜度)|BPP]]'''）。
* 新的诸如[[量子计算机]]这样的计算模型，可能可以快速的解决一些尚未知道是否属于'''P'''的问题；但是，没有一个它们已知能够解决的问题是'''NP'''完全的。不过，必须注意到'''P'''和'''NP'''问题的'''定义'''是采用像图灵机这样的经典计算模型的术语表述的。所以，即使一个量子计算机算法獲发现能有效解决一个'''NP'''完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类'''P'''和'''NP'''相等的证明。


== P≠NP的觀點 ==
多数计算机科学家相信'''P'''&ne;'''NP'''。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了（[[Karp的21个NP完全问题]]，在最早发现的一批中，有所有著名的已经存在的问题]]）。进一步地，P = NP这样的结果会导出很多惊人的结果，那些结果现在被相信是不成立的，例如NP = [[余NP]]和P = [[PH (复杂度)|PH]]。
{{who|多数计算机科学家}}相信'''P'''≠'''NP'''<ref>{{cite web |title=P≠NP - 百度学术 |url=https://xueshu.baidu.com/s?wd=P%E2%89%A0NP&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8&sc_hit=1 |website=xueshu.baidu.com |accessdate=2024-05-12 |archive-date=2024-05-12 |archive-url=https://web.archive.org/web/20240512072429/https://xueshu.baidu.com/s?wd=P%E2%89%A0NP&tn=SE_baiduxueshu_c1gjeupa&ie=utf-8&sc_hit=1 |dead-url=no }}</ref>。该信念的一个关键原因是经过数十年对这些问题的研究，没人能发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法（[[Karp的21个NP完全问题]]，在最早发现的一批中，有所有著名的已经存在的问题）。进一步，P=NP这样的结果会导致很多惊人结果，那些结果现在被相信不成立，如NP=[[反NP]]和P=[[PH (复杂度)|PH]]。


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


从另一方面讲，某些研究者认为我们过于相信'''P''' &ne; '''NP'''，而应该也去寻找'''P''' = '''NP'''的证明。例如，2002年中有这样的声明： [http://www.cs.umd.edu/~gasarch/papers/poll.ps]
从另一方面讲，某些研究者认为我们过于相信'''P'''≠'''NP'''，而应该也去寻找'''P'''='''NP'''的证明。例如，2002年有这声明：<ref name="poll">{{Cite journal|author=William I. Gasarch|title=The P=?NP poll.|journal=SIGACT News|volume=33|issue=2|pages=34–47|url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf|doi=10.1145/1052796.1052804|format=PDF|accessdate=29 December 2008|date=June 2002|archive-date=2019-10-27|archive-url=https://web.archive.org/web/20191027015501/http://www.cs.umd.edu/~gasarch/papers/poll.pdf|dead-url=no}}</ref>
: 倾向P&ne;NP的主要论据是在穷尽搜索的领域完全没有本质进展。也就是说，以我的观点，一个很弱的论据。算法的空间是很大的，而我们只是在开始探索的起点。[ . . . ] [[费马最后定理]]的解决也显示非常简单的[sic]问题可能只有用非常深刻的理论才能解决。
{{Cquote|倾向P≠NP的主要论据是在穷举搜索领域完全没有本质性进展。也就是说，以我的观点，这是一个很弱的论据。算法的空间非常大，而我们只是在开始探索的起点。……[[费马最后定理]]的解决也显示非常简单的问题可能只有用非常深刻的理论才能解决。|{{lang|en|Moshe Y. Vardi}}，[[莱斯大学]]}}
{{Cquote|过分依赖某种投机的猜測不是规划研究的一个好导引。我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。|{{lang|en|Anil Nerode}}，[[康奈尔大学]]}}
: &mdash; Moshe Vardi，[[莱斯大学]]
: 过分依赖某种投机不是规划研究的一个好的导引。我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。
: &mdash; Anil Nerode, [[康奈尔大学]]


==关于证明的难度的结果==
== 关于证明的难度的结果 ==
虽然百万美元的奖金和投入巨大却没有实质性结果的大量研究足以显示该问题很难，但是还有一些形式化的结果证明为什么该问题可能很难解决。


最常引用的结果之一是设计[[神諭機器|神諭]]。假想你有部魔法机器可以解决单一问题，例如「判定某数是否质数」，這魔法機器可以瞬间解决这问题。我们的新问题是，若我们獲允许任意利用这机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，'''P'''='''NP'''和'''P'''≠'''NP'''二者都可以证明。这个结论带来的后果是，任何可以通过修改[[神諭機器|神諭]]来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在'''相对化'''）。
虽然百万美元的奖金和大量投入巨大却没有实质性结果的研究足以显示该问题是困难的，还有一些形式化的结果证明为什么该问题可能很难解决。


如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决'''P'''='''NP'''问题。[http://www-2.cs.cmu.edu/~rudich/papers/natural.ps]{{Wayback|url=http://www-2.cs.cmu.edu/~rudich/papers/natural.ps |date=20050327012812 }}这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类定理得到证明，该定理的可能证明方法有越来越多的陷阱要规避。


这实际上也是为什么'''NP'''完全问题有用的原因－若对于NP完全问题存在有一个多项式时间算法，或者没有这样的算法，这将能用一种相信不被上述结果排除在外的方法来解决'''P'''='''NP'''问题。
最常被引用的结果之一设计[[神喻机器|神喻]]。假想你有一个魔法机器可以解决单个问题，例如决定一个给定的数字是否为质数，但可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，'''P''' = '''NP'''和'''P''' &ne; '''NP'''二者都可以证明。这个结论的后果是，任何可以修改来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在''相对化''）。


== 多項式時間演算法 ==
如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决'''P''' = '''NP'''问题。[http://www-2.cs.cmu.edu/~rudich/papers/natural.ps] 这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。
沒人知道多項式時間演算法對於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完全语言的多项式时间算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。
==多项式时间算法==

没人知道多项式时间算法对于NP完全问题是否存在。但是如果这样的算法存在，我们已经知道其中的一些了！例如，下面的算法正确的接受了一个NP完全语言，但是没人知道通常它需要多久运行。它是一个多项式时间算法当且仅当'''P''' = '''NP'''。

// 接受NP完全语言的一个算法[[子集和问题|子集和]]。
//
// 这是一个多项式时间算法当且仅当P=NP。
//
// “多项式时间”表示它在多项式时间内返回“是”，若
// 结果是“是”，否则永远运行。
//
// 输入：S = 一个自然数的有限集
// 输出："是" 如果某个S的子集加起来等于0。
// 否则，它永远运行没有输出。
// 注意: "程序数P" 是你将一个整数P写为二进制，然后
// 将位串考虑为一个程序。
// 每个可能的程序都可以这样产生，
// 虽然多数什么也不做因为有语法错误。
// <br>
FOR N = 1...infinity
FOR P = 1...N
以S为输入运行程序数P N步
IF 程序输出一个不同的整数的列表
AND 所有整数都在S中
AND 整数的和为0<br>
THEN
OUTPUT "是" 并 停机

若'''P''' = '''NP'''，则这是一个接受一个NP完全语言的多项式时间算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。


可能我们想要“解决”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？没有人知道。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句：
可能我们想要“解决”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？没有人知道。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句：


-{}-
IF 程序输出一个完整的数学证明
AND 证明的每一步合法
IF程序輸出一個完整的數學證明
AND 结论是S确实有（或者没有）一个和为0的子集
AND證明的每一步合法
AND結論是S確實有（或者沒有）一個和為0的子集
THEN
THEN
OUTPUT "是" （或者"不是"如果那被证明了）并停机
OUTPUT "是"（如果獲證實，就"不是"）並停機


==逻辑表述==
== 逻辑表述 ==
P=NP问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用[[一阶逻辑]]加上[[最小不动点]]操作（实际上，这允许了递归函数的定义）来表达。类似，NP是可以用存在性[[二阶逻辑]]来表达—也就是，在关系、函数、和子集上排除了[[全称量词]]的二阶逻辑。[[多项式等级]]，[[PH (复杂度)|PH]]中的语言对应与所有的[[二阶逻辑]]。这样，“P是NP的真子集吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”


== 花絮 ==
P=NP问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用[[一阶逻辑]]加上[[最小不动点]]操作（实际上，这允许了递归函数的定义）来表达。类似地，NP是可以用存在性[[二阶逻辑]]来表达&mdash;也就是，在关系、函数、和子集上排除了[[全域量词]]的二阶逻辑。[[多项式等级]]，[[PH (复杂度)|PH]]中的语言对应与所有的[[二阶逻辑]]。这样，“P是NP的真子集吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”
[[普林斯顿大学]]计算机系楼将[[二进制代码]]表述的“P=NP？”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。<ref>{{Cite web |url=https://www.cs.princeton.edu/general/images/csbricksjpg |title=https://www.cs.princeton.edu/general/images/csbricksjpg |accessdate=2018-10-04 |archive-date=2019-02-17 |archive-url=https://web.archive.org/web/20190217120638/https://www.cs.princeton.edu/general/images/csbricksjpg |dead-url=no }}</ref>
<ref>{{Cite web |url=https://www.cs.princeton.edu/general/bricks |title=https://www.cs.princeton.edu/general/bricks |accessdate=2018-10-04 |archive-date=2017-12-14 |archive-url=https://web.archive.org/web/20171214081659/http://www.cs.princeton.edu/general/bricks |dead-url=no }}</ref>


[[康奈尔大学]]的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：<ref>{{Cite web |url=http://www.cs.cornell.edu/hubes/pnp.htm |title=http://www.cs.cornell.edu/hubes/pnp.htm |accessdate=2005-07-15 |archive-date=2005-09-27 |archive-url=https://web.archive.org/web/20050927204236/http://www.cs.cornell.edu/hubes/pnp.htm |dead-url=no }}</ref>
==花絮==
{{quote|
[[普林斯顿大学]]计算机系楼将[[二进制代码]]表述的“P=NP?”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。[http://www.princeton.edu/~taubetap/tours/handbook.pdf]
反证法。设P{{=}}NP。令y为一个P{{=}}NP的证明。证明y可以用一个合格的-{zh-cn:计算机;zh-tw:電腦}-科学家在多项式时间内验证，我们认定这样的科学家的存在性为真，但因为P{{=}}NP，该证明y可在多项式时间内由这样的科学家发现，但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。}}


==註釋 ==
[[康奈尔大学]]的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：“<i>反证法。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。</i>"[http://www.cs.cornell.edu/hubes/pnp.htm]
{{Reflist|2}}


==参看==
==参考文献==
{{refbegin}}
*[[P (复杂度)]]
* Gerhard J. Woeginger. [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm The P-versus-NP page]{{Wayback|url=http://www.win.tue.nl/~gwoegi/P-versus-NP.htm |date=20050715082404 }}。Lists a number of incorrect solutions to the problem.
*[[NP (复杂度)]]
*[[NP完全]]

==外部链接及参考==

* [http://www.claymath.org/prizeproblems/index.htm The Clay Math Institute Millennium Prize Problems]
* Gerhard J. Woeginger. [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm 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.
* 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.
* 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.
* [[Neil Immerman]]。Languages Which Capture Complexity Classes. ''15th ACM STOC Symposium'', pp.347-354. 1983.
{{refend}}
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]
* [http://www.cse.iitk.ac.in/news/primality.html Manindra Agarwal, Nitin Saxena, Neeraj Kayal, "PRIMES is in P", Preprint, August 6, 2002]
* [http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html The "PRIMES is in P" FAQ]
* [http://www.complexityzoo.com Scott Aaronson's Complexity Zoo]


==延伸閱讀==
<!--{{复杂度类}}-->
{{refbegin|2}}
* {{cite journal| doi =10.1007/3-540-10843-2_23| year =1981| title =Computing a Perfect Strategy for n*n Chess Requires Time Exponential in N.| first1 =A. S.| last1 =Fraenkel| first2 =D.| last2 =Lichtenstein| journal =Lecture Notes in Computer Science| volume =| issue =| pages =278–293| url =http://www.pubzone.org/dblp/conf/icalp/FraenkelL81| format =| accessdate =| archive-date =2017-04-25| archive-url =https://web.archive.org/web/20170425031512/http://www.pubzone.org/dblp/conf/icalp/FraenkelL81| dead-url =yes}}
* {{cite book | last1 = Garey | first1 = Michael | last2 = Johnson | first2 = David | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | url = https://archive.org/details/computersintract0000gare | publisher = [[W. H. Freeman and Company]] | location = San Francisco | year = 1979 | isbn = 0-7167-1045-5 }}
* {{cite book | last = Goldreich | first = Oded | title = P, Np, and Np-Completeness | publisher = Cambridge University Press | location = Cambridge | year = 2010 | isbn = 978-0-521-12254-2 }} [http://www.wisdom.weizmann.ac.il/~oded/bc-drafts.html Online drafts]{{Wayback|url=http://www.wisdom.weizmann.ac.il/~oded/bc-drafts.html |date=20180123073733 }}
* {{Cite journal | last1 = Immerman | first1 = N. | title = Languages which capture complexity classes | pages = 760–778 | year = 1987 | journal = SIAM Journal on Computing | volume = 16 | issue = 4 | doi = 10.1137/0216051 | url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.4936 | access-date = 2018-01-19 | archive-date = 2013-04-29 | archive-url = https://web.archive.org/web/20130429170532/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.4936 | dead-url = no }}
* {{cite book | last = Cormen | first = Thomas | title = [[Introduction to Algorithms]] | publisher = [[MIT Press]] | location = Cambridge | year = 2001 | isbn = 0-262-03293-7 }}
* {{cite book | last = Papadimitriou | first = Christos | title = Computational Complexity | url = https://archive.org/details/computationalcom0000papa | publisher = Addison-Wesley | location = Boston | year = 1994 | isbn = 0-201-53082-1 }}
* {{Cite journal | last1 = Fortnow | first1 = L. | doi = 10.1145/1562164.1562186 | title = The Status of the P versus NP problem | journal = Communications of the ACM | volume = 52 | issue = 9 | pages = 78 | year = 2009 | url = http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext | pmid = | pmc = | access-date = 2018-01-19 | archive-date = 2017-02-15 | archive-url = https://web.archive.org/web/20170215201755/http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext | dead-url = no }}
* {{cite web | last1 = Fortnow | first1 = L. | last2 = Gasarch | first2 = W. | title = Computational complexity | url = http://weblog.fortnow.com | accessdate = 2019-04-27 | archive-date = 2009-05-01 | archive-url = https://web.archive.org/web/20090501175410/http://weblog.fortnow.com/ | dead-url = no }}
{{refend}}


== 外部链接 ==
* [http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html 未來數學家的挑戰（P與NP的簡介，清楚明瞭）]{{Wayback|url=http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html |date=20061011151657 }}{{zh-hant}}
* [https://web.archive.org/web/20051126011639/http://www.claymath.org/prizeproblems/index.htm The Clay Math Institute Millennium Prize Problems]
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]{{Wayback|url=http://www.ics.uci.edu/~eppstein/cgt/hard.html |date=20061206012118 }}
* [https://web.archive.org/web/20050716082540/http://www.cse.iitk.ac.in/news/primality.html Manindra Agarwal, Nitin Saxena, Neeraj Kayal, "PRIMES is in P", Preprint, August 6, 2002]
* [https://web.archive.org/web/20050723210919/http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html The "PRIMES is in P" FAQ]
* [http://www.complexityzoo.com Scott Aaronson's Complexity Zoo]{{Wayback|url=http://www.complexityzoo.com/ |date=20081204193604 }}


== 参见 ==
[[Category:复杂度类]]
* [[P (复杂度)]]
* [[NP (复杂度)]]
* [[NP完全]]
* [[未解決的數學問題|未解決數學問題]]
* [[NP-complete問題列表]]
* [[幾乎完備]]（{{tsl|en|Almost complete|Almost complete}}）問題與[[弱完備]]（{{tsl|en|weakly complete|weakly complete}}）問題
* [[ASR-complete]]
* [[Ladner理論]]
* [[NP困难]]

{{-}}
{{复杂度类}}

[[Category:複雜度類]]
[[Category:猜想]]
[[Category:猜想]]
[[Category:数学中未解决的问题]]
[[Category:数学中未解决的问题]]
[[Category:千禧年大奖难题]]

[[Category:计算机科学中未解决的问题]]
[[de:P/NP-Problem]]
[[en:Complexity classes P and NP]]
[[fi:P=NP]]
[[fr:Classes de complexité P et NP]]
[[he:P=NP]]
[[it:Classi di complessità P e NP]]
[[ja:P≠NP予想]]
[[ko:P-NP 문제]]
[[th:กลุ่มความซับซ้อน พี และ เอ็นพี]]

2024年10月6日 (日) 09:29的最新版本

未解決的計算機科學問題：如果一个问题的解可以快速检验正确性，那么这个问题一定可以快速求解吗？
千禧年大獎難題

P/NP问题是理论计算机科学中计算复杂度理论领域至今未解决的问题，是克雷数学研究所七題千禧年大奖难题之一。P/NP问题包括复杂度类P与NP的关系。1971年由史提芬·古克（Stephen A. Cook）和列昂尼德·列文（英语：Leonid Levin）分別提出。

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的复杂度类的图解。如P=NP则三个类相同。

簡單來說，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之外，所以需要比多项式时间更多的时间。判定皮尔斯伯格算术（英语：Presburger arithmetic）中的命题是否为真的问题更加困难。Fischer和Rabin（英语：Michael O. 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和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可在多项式时间内由这样的科学家发现，但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。

註釋

[编辑]
  1. ^ Wayback Machine（网页存档）. web.archive.org. 2005-04-04 [2017-09-05]. （原始内容存档于2005-04-04）. 
  2. ^ P≠NP - 百度学术. xueshu.baidu.com. [2024-05-12]. （原始内容存档于2024-05-12）. 
  3. ^ 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）. 
  4. ^ https://www.cs.princeton.edu/general/images/csbricksjpg. [2018-10-04]. （原始内容存档于2019-02-17）.  外部链接存在于|title= (帮助)
  5. ^ https://www.cs.princeton.edu/general/bricks. [2018-10-04]. （原始内容存档于2017-12-14）.  外部链接存在于|title= (帮助)
  6. ^ 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.

延伸閱讀

[编辑]

外部链接

[编辑]

参见

[编辑]
检索自“https://zh.wikipedia.org/zhwiki/w/index.php?title=P/NP问题&oldid=84483763”