P/NP問題

導入

P/NP問題是在理論信息學中計算複雜度理論領域裏至今沒有解決的問題，它被「克雷數學研究所」(Clay Mathematics Institute, 簡稱CMI)在千禧年大獎難題中收錄。P/NP問題中包含了複雜度類 P與NP的關係。1971年史提芬·古克和 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類不交。

本質上，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^(2^(cn))的運行時間，c為某個常數。這裏，n是Presburger命題的長度。因此，該命題已知需要比指數時間更多的運行時間。不可判定問題是更加困難的，例如停機問題。它們無法在任何給定時間內解決。

P真的容易處理嗎？

上面所有的討論假設了P表示「容易」而「不在P中」表示「困難」。這是一個在複雜度理論中常見而且有一定準確性的假設，它在實踐中卻不總是真的，原因包括如下幾點：

它忽略了常數因子。一個需要10¹⁰⁰⁰n時間的問題是屬於P的（它是線性時間的），但是事實上完全無法處理。一個需要10^-100002ⁿ時間的問題不是在P中的（它是指數時間的），但是對於n 取值直到幾千時還是很容易處理的。
它忽略了指數的大小。一個時間複雜度n¹⁰⁰⁰屬於P，但是很難對付。已經證明在P中存在需要任意大的指數的問題（參看時間等級定理）。一個時間複雜度2^n/1000的問題不屬於P，但對與n直到幾千還是容易應對的。
它只考慮了最壞情況的複雜度。可能現實世界中的有些問題在多數時候可以在時間n中解決，但是很偶爾你會看到需要時間2ⁿ的特例。這個問題可能有一個多項式的平均時間，但最壞情況是指數式的，所以該問題不屬於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)，這和我們日常經驗是相符的。

參看

外部連結及參考

The Clay Math Institute Millennium Prize Problems
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.
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