跳转到内容

P/NP问题：修订间差异

维基百科，自由的百科全书
以互动方式浏览历史
←上一版本下一版本→
删除的内容 添加的内容
可视化wikitext
Pioneerlike（留言 | 贡献）
38次编辑
小 →P 和NP：​ 較精確的語言描述
小 恢复到SDiZ的最后一次编辑
第1行： 第1行：
{{千禧年難題}}
{{千禧年难题}}


<!--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-->
<!--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) 和 [[:en:Leonid Levin|Leonid Levin]] 相對獨立的提出了下面的問題,即是否兩個複雜度類P和NP是恒等的（P=NP?）。
'''P/NP问题'''是在[[理论信息学]]中[[计算复杂度理论]]领域里至今没有解决的问题，它被“[[克雷数学研究所]]”（Clay Mathematics Institute, 简称CMI）在[[千禧年大奖难题]]中收录。P/NP问题中包含了[[复杂度类]][[P]]与[[NP]]的关系。1971年[[史提芬·古克]](Stephen A. Cook) 和 [[:en:Leonid Levin|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个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。[http://www.cs.umd.edu/~gasarch/papers/poll.ps] 对于正确的解答，有一个[[Clay Mathematics Institute|$1,000,000美元的奖励]]。


[[NP-完全]]問題(或者叫'''NPC''')的集合在這個討論中有重大作用，它們可以大致被描述為 — 在'''NP'''集合中卻不包含於'''P'''的元素，請注意這只是一個假設。(確切定義細節請參看[[NP-完全]])理論[[電腦科學家]]現在相信'''P''', '''NP''',和'''NPC'''類之間的關係如圖中所示，其中'''P'''和'''NPC'''類不交。
[[NP-完全]]问题(或者叫'''NPC''')的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在'''NP'''中最不像在'''P'''中的。(确切定义细节请参看[[NP-完全]])理论[[计算机科学家]]现在相信'''P''', '''NP''',和'''NPC'''类之间的关系如图中所示，其中'''P'''和'''NPC'''类不交。
[[Image:Complexity classes (en).svg|thumb|250px|假設'''P''' &ne; '''NP'''的複雜度類的圖解.如'''P''' = '''NP'''則三個類相同.]]
[[Image:Complexity classes (en).svg|thumb|250px|假设'''P''' &ne; '''NP'''的复杂度类的图解.如'''P''' = '''NP'''则三个类相同.]]


簡單來說，'''P''' = '''NP'''問題問道：如果是/不是問題的正面答案可以很快''驗證''，其答案是否也可以很快''計算''？這裏有一個給你找點這個問題的感覺的例子。給定一個大數''Y'',我們可以問''Y''是否是[[合數|複合數]]。例如，我們可能問53308290611是否有非平凡的因數。回答是肯定的，雖然手工找出一個因數很麻煩。從另一個方面講，如果有人聲稱答案是"對，因為224737可以整除53308290611",則我們可以很快用一個除法來驗證。驗證一個數是除數比首先找出除數來簡單得多。用於驗證一個正面答案所需的資訊也稱為''證書''。所以我們的結論是，給定 正確的證書，問題的正面答案可以很快的(也就是，在多項式時間內)驗證，而這就是這個問題屬於'''NP'''的原因。雖然這個特定的問題，最近被證明為也在'''P'''類中(參看[[#外部鏈結和參考|下面的]]關於"質數在P中"的參考),這一點也不明顯，而且有很多類似的問題相信不屬於類'''P'''。
簡單來說，'''P''' = '''NP'''问题问道：如果是/不是问题的正面答案可以很快''验证''，其答案是否也可以很快''计算''？这里有一个给你找点这个问题的感觉的例子。给定一个大数''Y'',我们可以问''Y''是否是[[合数|复合数]]。例如，我们可能问53308290611是否有非平凡的因子。回答是肯定的，虽然手工找出一个因子很麻烦。从另一个方面讲，如果有人声称答案是"对，因为224737可以整除53308290611",则我们可以很快用一个除法来验证。验证一个数是除数比首先找出除数来简单得多。用于验证一个正面答案所需的信息也称为''证书''。所以我们的结论是，给定 正确的证书，问题的正面答案可以很快的(也就是，在多项式时间内)验证，而这就是这个问题属于'''NP'''的原因。虽然这个特定的问题，最近被证明为也在'''P'''类中(参看[[#外部链接和参考|下面的]]关于"质数在P中"的参考),这一点也不明显，而且有很多类似的问题相信不属于类'''P'''。


限制到是/不是問題並沒有改變問題；即使我們允許更複雜的答案，最後的問題(是否[[FP (複雜度)|FP]] = [[FNP (複雜度)|FNP]])是等價的。
限制到是/不是问题并没有改变问题；即使我们允许更复杂的答案，最后的问题(是否[[FP (复杂度)|FP]] = [[FNP (复杂度)|FNP]])是等价的。


==形式化定義==
==形式化定义==


更正式一些，一個''決定問題''是一個取一些[[字串]]為輸入並要求輸出為是或否的問題。若有一個[[演算法]]（譬如[[圖靈機]]，或一個[[Lisp編程語言|LISP]]或[[Pascal編程語言|Pascal]]的程式並有無限的記憶體）能夠在最多''n''<sup>''k''</sup>步內對一個串長度為''n''的輸入給出正確答案，其中''k''是某個不依賴於輸入串的常數，則我們稱該問題可以在''多項式時間''內解決，並且將它置入類'''P'''。直觀的講，我們將'''P'''中的問題視為可以較快解決的問題。
更正式一些，一个''决定问题''是一个取一些[[字符串]]为输入并要求输出为是或否的问题。若有一个[[算法]]（譬如[[图灵机]]，或一个[[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''）。進一步假設
现在假设有一个算法A(''w'',''C'')取两个参数，一个串''w''，也就是我们的决定问题的输入串，而另一个串''C''是“建议证明”，并且使得A在最多''n''<sup>''k''</sup>步之内产生“是/否”答案（其中''n''是''w''的长度而''k''不依赖于''w''）。进一步假设
: ''w''是一個答案為“是”的例子，當且僅當，存在''C''使得A(''w'',''C'')返回“是”。
: ''w''是一个答案为“是”的例子，当且仅当，存在''C''使得A(''w'',''C'')返回“是”。
則我們稱這個問題可以在''非決定性多項式時間''內解決，且將它放入'''NP'''類。我們把演算法A作為一個所建議的證明的檢驗器，它運行足夠快。（注意縮寫'''NP'''代表“'''N'''on-deterministic（非確定性）'''P'''olynomial（多項式）”而''不是''代表“'''N'''on-'''P'''olynomial（非多項式）。）
则我们称这个问题可以在''非决定性多项式时间''内解决，且将它放入'''NP'''类。我们把算法A作为一个所建议的证明的检验器，它运行足够快。（注意缩写'''NP'''代表“'''N'''on-deterministic（非确定性）'''P'''olynomial（多项式）”而''不是''代表“'''N'''on-'''P'''olynomial（非多项式）。）


==NP完全==
==NP完全==


要解決'''P''' = '''NP'''問題，[[NP完全|'''NP'''完全]]的概念非常有用。不嚴格的講，'''NP'''完全問題是'''NP'''類中“最難”的問題，也就是說它們是最可能不屬於'''P'''類的。這是因為''任何'''''NP'''中的問題可以在多項式時間內變換成為任何特定'''NP'''完全問題的一個特例。例如，[[旅行商問題]]的判定問題版本是'''NP'''完全的。所以'''NP'''中的''任何''問題的''任何''特例可以在多項式時間內機械地轉換成旅行商問題的一個特例。
要解决'''P''' = '''NP'''问题，[[NP完全|'''NP'''完全]]的概念非常有用。不严格的讲，'''NP'''完全问题是'''NP'''类中“最难”的问题，也就是说它们是最可能不属于'''P'''类的。这是因为''任何'''''NP'''中的问题可以在多项式时间内变换成为任何特定'''NP'''完全问题的一个特例。例如，[[旅行商问题]]的判定问题版本是'''NP'''完全的。所以'''NP'''中的''任何''问题的''任何''特例可以在多项式时间内机械地转换成旅行商问题的一个特例。
所以若旅行商問題被證明為在'''P'''內，則'''P ''' = '''NP'''！旅行商問題是很多這樣的'''NP'''完全的問題之一。若任何一個'''NP'''完全的問題在'''P'''內，則可以推出'''P''' = '''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'''='''NP'''还是未知的，在'''P'''之外的问题是已经知道存在的。寻找[[国际象棋]]或[[围棋]]最佳走法（在''n''乘''n''棋盘上）是[[指数时间完全]]的。因为可以证明P &ne; EXPTIME（指数时间），这些问题位于'''P'''之外，所以需要比多项式时间更多的时间。判定[[Presburger算术]]中的命题是否为真的问题更加困难。Fischer和[[Michael O. Rabin|Rabin]]于[[1974年]]证明每个决定Presburger命题的真伪性的算法有最少2^(2^(''cn''))的运行时间，''c''为某个常数。这里，''n''是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如[[停机问题]]。它们无法在任何给定时间内解决。


==P真的容易處理嗎？==
==P真的容易处理吗？==


上面所有的討論假設了'''P'''表示“容易”而“不在'''P'''中”表示“困難”。這是一個在複雜度理論中常見而且有一定準確性的假設，它在實踐中卻不總是真的，原因包括如下幾點：
上面所有的讨论假设了'''P'''表示“容易”而“不在'''P'''中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点：
*它忽略了常數因數。一個需要10<sup>1000</sup>''n''時間的問題是屬於'''P'''的（它是線性時間的），但是事實上完全無法處理。一個需要10<sup>-10000</sup>2<sup>''n''</sup>時間的問題不是在'''P'''中的（它是指數時間的），但是對於''n'' 取值直到幾千時還是很容易處理的。
*它忽略了常数因子。一个需要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''<sup>1000</sup>属于'''P'''，但是很难对付。已经证明在'''P'''中存在需要任意大的指数的问题（参看[[时间等级定理]]）。一个时间复杂度2<sup>''n''/1000</sup>的问题不属于'''P'''，但对与''n''直到几千还是容易应对的。
*它只考慮了最壞情況的複雜度。可能現實世界中的有些問題在多數時候可以在時間''n''中解決，但是很偶爾你會看到需要時間2<sup>''n''</sup>的特例。這個問題可能有一個多項式的平均時間，但最壞情況是指數式的，所以該問題不屬於'''P'''。
*它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间''n''中解决，但是很偶尔你会看到需要时间2<sup>''n''</sup>的特例。这个问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于'''P'''。
*它只考慮確定性解。可能有一個問題你可以很快解決如果你可以接受出現一點誤差的可能，但是確保正確的答案會難得多。這個問題不會屬於'''P'''，雖然事實上它可以很快求解。這實際上是解決屬於'''NP'''而還不知道是否屬於'''P'''的問題的一個辦法（參看'''[[RP (複雜度)|RP]]'''， '''[[BPP]]'''）。
*它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于'''P'''，虽然事实上它可以很快求解。这实际上是解决属于'''NP'''而还不知道是否属于'''P'''的问题的一个办法（参看'''[[RP (复杂度)|RP]]'''， '''[[BPP]]'''）。
*新的諸如[[量子電腦]]這樣的計算模型，可能可以快速的解決一些尚未知道是否屬於'''P'''的問題；但是，沒有一個它們已知能夠解決的問題是'''NP'''完全的。不過，必須注意到'''P'''和'''NP'''問題的''定義''是採用象圖靈機這樣的經典計算模型的屬於表述的。所以，即使一個量子電腦演算法被發現能夠有效的解決一個'''NP'''完全問題，我們只是有了一個快速解決困難問題的實際方法，而不是數學類'''P'''和'''NP'''相等的證明。
*新的诸如[[量子计算机]]这样的计算模型，可能可以快速的解决一些尚未知道是否属于'''P'''的问题；但是，没有一个它们已知能够解决的问题是'''NP'''完全的。不过，必须注意到'''P'''和'''NP'''问题的''定义''是采用象图灵机这样的经典计算模型的属于表述的。所以，即使一个量子计算机算法被发现能够有效的解决一个'''NP'''完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类'''P'''和'''NP'''相等的证明。


==電腦科學家為什麼認為P &ne; NP？==
==计算机科学家为什么认为P &ne; NP？==


多數電腦科學家相信'''P'''&ne;'''NP'''。該信念的一個關鍵原因是經過數十年對這些問題的研究，沒有人能夠發現一個NP完全問題的多項式時間演算法。而且，人們早在NP完全的概念出現前就開始尋求這些演算法了（[[Karp的21個NP完全問題]]，在最早發現的一批中，有所有著名的已經存在的問題]]）。進一步地，P = NP這樣的結果會導出很多驚人的結果，那些結果現在被相信是不成立的，例如NP = [[餘NP]]和P = [[PH (複雜度)|PH]]。
多数计算机科学家相信'''P'''&ne;'''NP'''。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了（[[Karp的21个NP完全问题]]，在最早发现的一批中，有所有著名的已经存在的问题]]）。进一步地，P = NP这样的结果会导出很多惊人的结果，那些结果现在被相信是不成立的，例如NP = [[余NP]]和P = [[PH (复杂度)|PH]]。


也有這樣論證的：問題較難求解(NP)但容易驗證(P)，這和我們日常經驗是相符的。
也有这样论证的：问题较难求解(NP)但容易验证(P)，这和我们日常经验是相符的。


從另一方面講，某些研究者認為我們過於相信'''P''' &ne; '''NP'''，而應該也去尋找'''P''' = '''NP'''的證明。例如，2002年中有這樣的聲明： [http://www.cs.umd.edu/~gasarch/papers/poll.ps]
从另一方面讲，某些研究者认为我们过于相信'''P''' &ne; '''NP'''，而应该也去寻找'''P''' = '''NP'''的证明。例如，2002年中有这样的声明： [http://www.cs.umd.edu/~gasarch/papers/poll.ps]
: 傾向P&ne;NP的主要論據是在窮盡搜索的領域完全沒有本質進展。也就是說，以我的觀點，一個很弱的論據。演算法的空間是很大的，而我們只是在開始探索的起點。[ . . . ] [[費馬最後定理]]的解決也顯示非常簡單的[sic]問題可能只有用非常深刻的理論才能解決。
: 倾向P&ne;NP的主要论据是在穷尽搜索的领域完全没有本质进展。也就是说，以我的观点，一个很弱的论据。算法的空间是很大的，而我们只是在开始探索的起点。[ . . . ] [[费马最后定理]]的解决也显示非常简单的[sic]问题可能只有用非常深刻的理论才能解决。
: &mdash; Moshe Vardi，[[萊斯大學]]
: &mdash; Moshe Vardi，[[莱斯大学]]
: 過分依賴某種投機不是規劃研究的一個好的導引。我們必須總是嘗試每個問題的兩個方向。偏見可能導致著名的數學家無法解決答案和他們的預計相反的著名問題，雖然他們發展了所有所需的方法。
: 过分依赖某种投机不是规划研究的一个好的导引。我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。
: &mdash; Anil Nerode, [[康奈爾大學]]
: &mdash; Anil Nerode, [[康奈尔大学]]


==關於證明的難度的結果==
==关于证明的难度的结果==


雖然百萬美元的獎金和大量投入巨大卻沒有實質性結果的研究足以顯示該問題是困難的，還有一些形式化的結果證明為什麼該問題可能很難解決。
虽然百万美元的奖金和大量投入巨大却没有实质性结果的研究足以显示该问题是困难的，还有一些形式化的结果证明为什么该问题可能很难解决。




最常被引用的結果之一設計[[神喻機器|神喻]]。假想你有一個魔法機器可以解決單個問題，例如決定一個給定的數字是否為質數，但可以瞬間解決這個問題。我們的新問題是，若我們被允許任意利用這個機器，是否存在我們可以在多項式時間內驗證但無法在多項式時間內解決的問題？結果是，依賴於機器能解決的問題，'''P''' = '''NP'''和'''P''' &ne; '''NP'''二者都可以證明。這個結論的後果是，任何可以修改來證明該機器的存在性的結果不能解決問題。不幸的是，幾乎所有經典的方法和大部分已知的方法可以這樣修改（我們稱它們在''相對化''）。
最常被引用的结果之一设计[[神喻机器|神喻]]。假想你有一个魔法机器可以解决单个问题，例如决定一个给定的数字是否为质数，但可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，'''P''' = '''NP'''和'''P''' &ne; '''NP'''二者都可以证明。这个结论的后果是，任何可以修改来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在''相对化''）。


如果這還不算太糟的話，1993年Razborov和Rudich證明的一個結果表明，給定一個特定的可信的假設，在某種意義下“自然”的證明不能解決'''P''' = '''NP'''問題。[http://www-2.cs.cmu.edu/~rudich/papers/natural.ps] 這表明一些現在似乎最有希望的方法不太可能成功。隨著更多這類的定理得到證明，該定理的可能證明有越來越多的陷阱要規避。
如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决'''P''' = '''NP'''问题。[http://www-2.cs.cmu.edu/~rudich/papers/natural.ps] 这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。


這實際上也是為什麼NP完全問題有用的原因：若有一個多項式時間演算法，或者沒有一個這樣的演算法，對於NP完全問題存在，這將用一種相信不被上述結果排除在外的方法來解決'''P''' = '''NP'''問題。
这实际上也是为什么NP完全问题有用的原因：若有一个多项式时间算法，或者没有一个这样的算法，对于NP完全问题存在，这将用一种相信不被上述结果排除在外的方法来解决'''P''' = '''NP'''问题。


==多項式時間演算法==
==多项式时间算法==


沒人知道多項式時間演算法對於NP完全問題是否存在。但是如果這樣的演算法存在，我們已經知道其中的一些了！例如，下面的演算法正確的接受了一個NP完全語言，但是沒人知道通常它需要多久運行。它是一個多項式時間演算法當且僅當'''P''' = '''NP'''。
没人知道多项式时间算法对于NP完全问题是否存在。但是如果这样的算法存在，我们已经知道其中的一些了！例如，下面的算法正确的接受了一个NP完全语言，但是没人知道通常它需要多久运行。它是一个多项式时间算法当且仅当'''P''' = '''NP'''。


// 接受NP完全語言的一個演算法[[子集和問題|子集和]]。
// 接受NP完全语言的一个算法[[子集和问题|子集和]]。
//
//
// 這是一個多項式時間演算法當且僅當P=NP。
// 这是一个多项式时间算法当且仅当P=NP。
//
//
// “多項式時間”表示它在多項式時間內返回“是”，若
// “多项式时间”表示它在多项式时间内返回“是”，若
// 結果是“是”，否則永遠運行。
// 结果是“是”，否则永远运行。
//
//
// 輸入：S = 一個自然數的有限集
// 输入：S = 一个自然数的有限集
// 輸出："是" 如果某個S的子集加起來等於0。
// 输出："是" 如果某个S的子集加起来等于0。
// 否則，它永遠運行沒有輸出。
// 否则，它永远运行没有输出。
// 注意: "程式數P" 是你將一個整數P寫為二進位，然後
// 注意: "程序数P" 是你将一个整数P写为二进制，然后
// 將位元串考慮為一個程式。
// 将位串考虑为一个程序。
// 每個可能的程式都可以這樣產生，
// 每个可能的程序都可以这样产生，
// 雖然多數什麼也不做因為有語法錯誤。
// 虽然多数什么也不做因为有语法错误。
// <br>
// <br>
FOR N = 1...infinity
FOR N = 1...infinity
FOR P = 1...N
FOR P = 1...N
以S為輸入運行程式數P N步
以S为输入运行程序数P N步
IF 程式輸出一個不同的整數的列表
IF 程序输出一个不同的整数的列表
AND 所有整數都在S中
AND 所有整数都在S中
AND 整數的和為0<br>
AND 整数的和为0<br>
THEN
THEN
OUTPUT "是" 並 停機
OUTPUT "是" 并 停机


若'''P''' = '''NP'''，則這是一個接受一個NP完全語言的多項式時間演算法。“接受”表示它在多項式時間內給出“是”的答案，但允許在答案是“否”的時候永遠運行。
若'''P''' = '''NP'''，则这是一个接受一个NP完全语言的多项式时间算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。


可能我們想要“解決”子集和問題，而不是僅僅“接受”子集和語言。這表示我們想要它總是停機並返回一個“是”或“否”的答案。是否存在任何可能在多項式時間內解決這個問題的演算法？沒有人知道。但是如果這樣的演算法存在，那麼我們已經知道其中的一些了！只要將上面的演算法中的IF語句替換成下面的語句：
可能我们想要“解决”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？没有人知道。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句：


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


==邏輯表述==
==逻辑表述==


P=NP問題可以用邏輯命題的特定類的可表達性的術語來重新表述。所有P中的語言可以用[[一階邏輯]]加上[[最小不動點]]操作（實際上，這允許了遞迴函數的定義）來表達。類似地，NP是可以用存在性[[二階邏輯]]來表達&mdash;也就是，在關係、函數、和子集上排除了[[全域量詞]]的二階邏輯。[[多項式等級]]，[[PH (複雜度)|PH]]中的語言對應與所有的[[二階邏輯]]。這樣，“P是NP的真子集嗎”這樣的問題可以表述為“是否存在性二階邏輯能夠表達帶最小不動點操作的一階邏輯的所不能表達的語言？”
P=NP问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用[[一阶逻辑]]加上[[最小不动点]]操作（实际上，这允许了递归函数的定义）来表达。类似地，NP是可以用存在性[[二阶逻辑]]来表达&mdash;也就是，在关系、函数、和子集上排除了[[全域量词]]的二阶逻辑。[[多项式等级]]，[[PH (复杂度)|PH]]中的语言对应与所有的[[二阶逻辑]]。这样，“P是NP的真子集吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”


==花絮==
==花絮==
[[普林斯頓大學]]電腦系樓將[[二進位碼]]表述的“P=NP?”問題刻進頂樓西面的磚頭上。如果證明了P=NP，磚頭可以很方便的換成表示“P=NP！”。[http://www.princeton.edu/~taubetap/tours/handbook.pdf]
[[普林斯顿大学]]计算机系楼将[[二进制代码]]表述的“P=NP?”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。[http://www.princeton.edu/~taubetap/tours/handbook.pdf]


[[康奈爾大學]]的Hubert Chen博士提供了這個玩笑式的P不等於NP的證明：“<i>反證法。設P = NP。令y為一個P = NP的證明。證明y可以用一個合格的電腦科學家在多項式時間內驗證，我們認定這樣的科學家的存在性為真。但是，因為P = NP，該證明y可以在多項式時間內由這樣的科學家發現。但是這樣的發現還沒有發生（雖然這樣的科學家試圖發現這樣的一個證明），我們得到矛盾。</i>"[http://www.cs.cornell.edu/hubes/pnp.htm]
[[康奈尔大学]]的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：“<i>反证法。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。</i>"[http://www.cs.cornell.edu/hubes/pnp.htm]


==參看==
==参看==
*[[P (複雜度)]]
*[[P (复杂度)]]
*[[NP (複雜度)]]
*[[NP (复杂度)]]
*[[NP完全]]
*[[NP完全]]


==外部鏈結及參考==
==外部链接及参考==


* [http://www.claymath.org/prizeproblems/index.htm The Clay Math Institute Millennium Prize Problems]
* [http://www.claymath.org/prizeproblems/index.htm The Clay Math Institute Millennium Prize Problems]
第130行： 第130行：
* [http://www.complexityzoo.com Scott Aaronson's Complexity Zoo]
* [http://www.complexityzoo.com Scott Aaronson's Complexity Zoo]


<!--{{複雜度類}}-->
<!--{{复杂度类}}-->




[[Category:複雜度類]]
[[Category:复杂度类]]
[[Category:猜想]]
[[Category:猜想]]
[[Category:數學中未解決的問題]]
[[Category:数学中未解决的问题]]


[[ca:P versus NP]]
[[ca:P versus NP]]

2006年7月11日 (二) 03:50的版本

千禧年大獎難題

P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay Mathematics Institute, 简称CMI）在千禧年大奖难题中收录。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克(Stephen A. Cook) 和 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类不交。

File:Complexity classes (en).svg
假设P ≠ NP的复杂度类的图解.如P = NP则三个类相同.

簡單來說，P = NP问题问道：如果是/不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。给定一个大数Y,我们可以问Y是否是复合数。例如，我们可能问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棋盘上）是指数时间完全的。因为可以证明P ≠ EXPTIME（指数时间），这些问题位于P之外，所以需要比多项式时间更多的时间。判定Presburger算术中的命题是否为真的问题更加困难。Fischer和Rabin于1974年证明每个决定Presburger命题的真伪性的算法有最少2^(2^(cn))的运行时间，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。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了（Karp的21个NP完全问题，在最早发现的一批中，有所有著名的已经存在的问题]]）。进一步地，P = NP这样的结果会导出很多惊人的结果，那些结果现在被相信是不成立的，例如NP = 余NP和P = PH。

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

从另一方面讲，某些研究者认为我们过于相信P ≠ NP，而应该也去寻找P = NP的证明。例如，2002年中有这样的声明： [2]

倾向P≠NP的主要论据是在穷尽搜索的领域完全没有本质进展。也就是说，以我的观点，一个很弱的论据。算法的空间是很大的，而我们只是在开始探索的起点。[ . . . ] 费马最后定理的解决也显示非常简单的[sic]问题可能只有用非常深刻的理论才能解决。
— Moshe Vardi，莱斯大学
过分依赖某种投机不是规划研究的一个好的导引。我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。
— Anil Nerode, 康奈尔大学

关于证明的难度的结果

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


最常被引用的结果之一设计神喻。假想你有一个魔法机器可以解决单个问题，例如决定一个给定的数字是否为质数，但可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P = NP和P ≠ NP二者都可以证明。这个结论的后果是，任何可以修改来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。

如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P = NP问题。[3] 这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。

这实际上也是为什么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]

康奈尔大学的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：“反证法。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。"[5]

参看

外部链接及参考

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