P/NP問題

--問題是理論資訊學中計算複雜度理論領域至今未解決的問題，是克雷數學研究所七題千禧年大獎難題之一。P/NP問題包括複雜度類P與NP的關係。1971年由史提芬·古克和分別提出。P=NP.複雜度類P即為所有可以由一個確定型圖靈機在多項式表達的時間內解決的問題；類NP由所有可以在多項式時間內驗證它的解是否正確的決定問題組成，或者等效的說，那些可以在非確定型圖靈機上在多項式時間內找出解的問題的集合。很可能，計算理論最大的未解決問題就是關於這兩類的關係的：P和NP相等在2002年對於100研究者的調查中，61人相信答案是否定的，9人相信答案是肯定的，22人不確定，而8人相信問題可能和現在所接受的公理獨立，所以不可能證明或證否。對於正確的解答，有一個一百萬美元的獎勵。NP-完全問題。計算機科學家現在相信P、NP和NPC類之間的關係如圖中所示，其中P和NPC類不相交。簡單來說，P=NP即：「若問題的答案可以很快驗證，其答案是否也可以很快被計算出來。」例如某大數是否合數：如53308290611有否非平凡因數。答案是肯定的，雖然人手找出一個因數很麻煩。從另一個方面講，如果有人聲稱答案是「對，224737可以整除53308290611」，則我們可以很快用除法驗證。驗證一個數是除數比找出一個明顯除數來簡單得多。用於驗證一個正面答案所需的資訊也稱為證明。所以我們的結論是，給定正確的證明，問題的正面答案可以很快驗證，而這就是這個問題屬於NP的原因。雖然這個特定的問題，最近也獲證實在P類中，這一點也不明顯，而且有很多類似的問題相信不屬於類P。像上面這樣，把問題限制到“是／不是”問題並沒有改變原問題是等價的。學術定義.更正式一些，一個決定問題是一個取一些字串為輸入並要求輸出為是或否的問題。若有一個演算法能夠在最多nk步內對一個串長度為n的輸入給出正確答案，其中k是某個不依賴於輸入串的常數，則我們稱該問題可以在多項式時間內解決，並且將它置入類P。直觀的講，我們將P中的問題視為可以較快解決的問題。現在假設有一個演算法A(w,C)取兩個引數，一個串w，也就是我們的決定問題的輸入串，而另一個串C是“建議證明”，並且使得A在最多nk步內產生“是／否”答案。然後假設：w是一個答案為“是”的例子，當且僅當，存在C使得A(w,C)返回“是”。則我們稱這個問題可以在非決定性多項式時間內解決，且將它放入NP類。我們把演算法A作為一個所建議的證明的檢驗器，它執行足夠快。NP完全.要解決P=NP問題，NP完全的概念非常有用。不嚴格的講，NP完全問題是NP類中“最難”的問題，也就是說它們是最可能不屬於P類的。這是因為任何NP中的問題可以在多項式時間內變換成為任何特定NP完全問題的一個特例。例如，旅行推銷員問題的判定問題版本為NP完全。所以NP中的任何問題的任何特例可以在多項式時間內轉換成旅行商問題的一個特例。所以若旅行商問題能證實在P內，則P=NP。旅行商問題是很多這樣的NP完全的問題之一。若任何一個NP完全的問題在P內，則可以推出P=NP。不幸的是，雖然很多重要的問題被證實為NP完全，但卻沒有一個有已知快速的演算法。更難的問題.雖然是否P=NP還是未知的，在P之外的問題是已經知道存在的。尋找國際象棋或圍棋最佳走法，這些問題位於P之外，所以需要比多項式時間更多的時間。判定中的命題是否為真的問題更加困難。Fischer和於1974年證明每個決定Presburger命題的真偽性的演算法有最少22cn的執行時間，"c"為某個常數。這裡，"n"是Presburger命題的長度。因此，該命題已知需要比指數時間更多的執行時間。不可判定問題是更加困難的，例如停機問題，而它們無法在任何給定時間內解決。P真的容易處理嗎？.上面所有的討論，假設了P表示“容易”而“不在P中”表示“困難”。這是一個在複雜度理論中常見而且有一定準確性的假設，它在實踐中卻不總是真的，原因包括如下幾點：P≠NP的觀點.也有這樣論證：問題難求解，這和我們日常經驗相符。從另一方面講，某些研究者認為我們過於相信P≠NP，而應該也去尋找P=NP的證明。例如，2002年有這宣告：關於證明的難度的結果.雖然百萬美元的獎金和投入巨大卻沒有實質性結果的大量研究足以顯示該問題很難，但是還有一些形式化的結果證明為什麼該問題可能很難解決。最常引用的結果之一是設計神諭。假想你有部魔法機器可以解決單一問題，例如「判定某數是否質數」，這魔法機器可以瞬間解決這問題。我們的新問題是，若我們獲允許任意利用這機器，是否存在我們可以在多項式時間內驗證但無法在多項式時間內解決的問題？結果是，依賴於機器能解決的問題，P=NP和P≠NP二者都可以證明。這個結論帶來的後果是，任何可以透過修改神諭來證明該機器的存在性的結果不能解決問題。不幸的是，幾乎所有經典的方法和大部分已知的方法可以這樣修改。如果這還不算太糟的話，1993年Razborov和Rudich證明的一個結果表明，給定一個特定的可信的假設，在某種意義下“自然”的證明不能解決P=NP問題。這表明一些現在似乎最有希望的方法不太可能成功。隨著更多這類定理得到證明，該定理的可能證明方法有越來越多的陷阱要規避。這實際上也是為什麼NP完全問題有用的原因－若對於NP完全問題存在有一個多項式時間演算法，或者沒有這樣的演算法，這將能用一種相信不被上述結果排除在外的方法來解決P=NP問題。多項式時間演演算法.沒人知道多項式時間演演算法對於NP完全問題是否存在。但是如果這樣的演演算法存在，我們已經知道其中的一些了！例如下面的演算法正確地接受了一個NP完全語言，但是沒人知道通常它需要多久執行。它是一個多項式時間演演算法當且僅當P=NP。// 接受NP完全語言的一個演算法子集和。// 這是一個多項式時間演算法當且僅當P=NP。// “多項式時間”表示它在多項式時間內返回“是”，若// 結果是“是”，否則永遠執行。// 輸入：S = 一個自然數的有限集// 輸出："是"如果某個S的子集加起來等於0。// 否則，它永遠執行沒有輸出。// 注意: "程式數P"是你將一個整數P寫為二進位制，然後// 將位元串考慮為一個程式。// 每個可能的程式都可以這樣產生，// 雖然多數什麼也不做因為有語法錯誤。FOR N = 1...infinityFOR P = 1...N以S為輸入執行程式數P N步IF程式輸出一個不同的整數的列表AND所有整數都在S中AND整數的和為0THENOUTPUT "是"並 停機若P=NP，則這是一個接受一個NP完全語言的多項式時間演算法。“接受”表示它在多項式時間內給出“是”的答案，但允許在答案是“否”的時候永遠執行。可能我們想要“解決”子集和問題，而不是僅僅“接受”子集和語言。這表示我們想要它總是停機並返回一個“是”或“否”的答案。是否存在任何可能在多項式時間內解決這個問題的演算法？沒有人知道。但是如果這樣的演算法存在，那麼我們已經知道其中的一些了！只要將上面的演算法中的IF語句替換成下面的語句：IF程式輸出一個完整的數學證明AND證明的每一步合法AND結論是S確實有一個和為0的子集THENOUTPUT "是"並停機邏輯表述.P=NP問題可以用邏輯命題的特定類的可表達性的術語來重新表述。所有P中的語言可以用一階邏輯加上最小不動點操作來表達。類似，NP是可以用存在性二階邏輯來表達—也就是，在關係、函式、和子集上排除了全稱量詞的二階邏輯。多項式等級，PH中的語言對應與所有的二階邏輯。這樣，“P是NP的真子集嗎”這樣的問題可以表述為“是否存在性二階邏輯能夠表達帶最小不動點操作的一階邏輯的所不能表達的語言？”花絮.普林斯頓大學計算機系樓將二進位制程式碼表述的“P=NP？”問題刻進頂樓西面的磚頭上。如果證明了P=NP，磚頭可以很方便的換成表示“P=NP！”。康奈爾大學的Hubert Chen博士提供了這個玩笑式的P不等於NP的證明：反證法。設PNP。令y為一個PNP的證明。證明y可以用一個合格的-{zh-cn:計算機;zh-tw:電腦}-科學家在多項式時間內驗證，我們認定這樣的科學家的存在性為真，但因為PNP，該證明y可在多項式時間內由這樣的科學家發現，但是這樣的發現還沒有發生，我們得到矛盾。