基本介紹
- 中文名：P類問題
- 外文名：P versus NP problem
- 領域：理論信息學
- 別稱：NP問題、NPC問題
P=NP,學術定義,NP完全,更難的問題,P真的容易處理嗎？,關於證明的難度的結果,邏輯表述,
P=NP
複雜度類P即為所有可以由一個確定型圖靈機在多項式表達的時間內解決的問題；類NP由所有可以在多項式時間內驗證它的解是否正確的決定問題組成，或者等效的說，那些可以在非確定型圖靈機上在多項式時間內找出解的問題的集合。很可能，計算理論最大的未解決問題就是關於這兩類的關係的：P和NP相等。
在2002年對於100研究者的調查，61人相信答案是否定的，9個相信答案是肯定的，22個不確定，而8個相信該問題可能和現在所接受的公理獨立，所以不可能證明或證否。對於正確的解答，有一個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的運行時間，c為某個常數。這裡，n是Presburger命題的長度。因此，該命題已知需要比指數時間更多的運行時間。不可判定問題是更加困難的，例如停機問題。它們無法在任何給定時間內解決。
P真的容易處理嗎？
上面所有的討論，假設了P表示“容易”而“不在P中”表示“困難”。這是一個在複雜度理論中常見而且有一定準確性的假設，它在實踐中卻不總是真的，原因包括如下幾點：
- 它忽略了常數因子。一個需要10n時間的問題是屬於P的（它是線性時間的），但是事實上完全無法處理。一個需要102時間的問題不是在P中的（它是指數時間的），但是對於n取值直到幾千時還是很容易處理的。
- 它忽略了指數的大小。一個時間複雜度n屬於P，但是很難對付。已經證明在P中存在需要任意大的指數的問題（參看時間層次定理）。一個時間複雜度2的問題不屬於P，但對於n直到幾千還是容易應對的。
- 它只考慮了最壞情況的複雜度。可能現實世界中的有些問題在多數時候可以在時間n中解決，但是很偶爾你會看到需要時間2的特例。這個問題可能有一個多項式的平均時間，但最壞情況是指數式的，所以該問題不屬於P。
- 新的諸如量子計算機這樣的計算模型，可能可以快速的解決一些尚未知道是否屬於P的問題；但是，沒有一個它們已知能夠解決的問題是NP完全的。不過，必須注意到P和NP問題的定義是採用像圖靈機這樣的經典計算模型的術語表述的。所以，即使一個量子計算機算法被發現能夠有效的解決一個NP完全問題，我們只是有了一個快速解決困難問題的實際方法，而不是數學類P和NP相等的證明。
關於證明的難度的結果
雖然百萬美元的獎金和投入巨大卻沒有實質性結果的大量研究足以顯示該問題是困難的，但是還有一些形式化的結果證明為什麼該問題可能很難解決。
最常被引用的結果之一是設計神諭。假想你有一個魔法機器可以解決單個問題，例如判定一個給定的數是否為質數，可以瞬間解決這個問題。我們的新問題是，若我們被允許任意利用這個機器，是否存在我們可以在多項式時間內驗證但無法在多項式時間內解決的問題？結果是，依賴於機器能解決的問題，P=NP和P≠NP二者都可以證明。這個結論帶來的後果是，任何可以通過修改神諭來證明該機器的存在性的結果不能解決問題。不幸的是，幾乎所有經典的方法和大部分已知的方法可以這樣修改（我們稱它們在相對化）。
如果這還不算太糟的話，1993年Razborov和Rudich證明的一個結果表明，給定一個特定的可信的假設，在某種意義下“自然”的證明不能解決P=NP問題。
邏輯表述
P=NP問題可以用邏輯命題的特定類的可表達性的術語來重新表述。所有P中的語言可以用一階邏輯加上最小不動點操作（實際上，這允許了遞歸函式的定義）來表達。類似地，NP是可以用存在性二階邏輯來表達—也就是，在關係、函式、和子集上排除了全稱量詞的二階邏輯。多項式等級，PH中的語言對應與所有的二階邏輯。這樣，“P是NP的真子集嗎”這樣的問題可以表述為“是否存在性二階邏輯能夠表達帶最小不動點操作的一階邏輯的所不能表達的語言？”
這表明一些現在似乎最有希望的方法不太可能成功。隨著更多這類定理得到證明，該定理的可能證明方法有越來越多的陷阱要規避。
這實際上也是為什麼NP完全問題有用的原因：若對於NP完全問題存在有一個多項式時間算法，或者沒有一個這樣的算法，這將能用一種相信不被上述結果排除在外的方法來解決P=NP問題。
