P/NP问题

**P/NP 問題**是理論資訊學中計算複雜度理論領域至今未解決的問題，是克雷數學研究所七題千禧年大獎難題之一。P/NP 問題包括複雜度類別 P 與 NP 的關係。1971 年由史提芬・古克（Stephen A. Cook）和列昂尼德・列文分別提出。

## 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** 即：「若問題的答案可以很快驗證，其答案是否也可以很快被計算出來。」

例如某大數是否合數：如 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** 代表「**N**on-deterministic（非確定性）**P**olynomial（多項式）」而不是代表「**N**on-**P**olynomial（非多項式）。）

## 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** 之外，所以需要比多項式時間更多的時間。判定皮爾斯伯格算術中的命題是否為真的問題更加困難。Fischer 和 Rabin 於 1974 年證明每個決定 Presburger 命題的真偽性的演算法有最少 22cn 的執行時間，_c_ 為某個常數。這裡，_n_ 是 Presburger 命題的長度。因此，該命題已知需要比指數時間更多的執行時間。不可判定問題是更加困難的，例如停機問題，而它們無法在任何給定時間內解決。

## P 真的容易處理嗎？

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

* 它忽略了常數因子。一個需要 101000_n_ 時間的問題是屬於 **P** 的（它是線性時間的），但是事實上完全無法處理。一個需要 10-100002n 時間的問題不是在 **P** 中的（它是指數時間的），但是對於 _n_ 取值直到幾千時還是很容易處理的。
* 它忽略了指數的大小。一個時間複雜度 _n_1000 屬於 **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。

也有這樣論證：問題難求解（P）但易驗證（NP），這和我們日常經驗相符。

從另一方面講，某些研究者認為我們過於相信 **P**≠**NP**，而應該也去尋找 **P**=**NP** 的證明。例如，2002 年有這聲明：

## 關於證明的難度的結果

雖然百萬美元的獎金和投入巨大卻沒有實質性結果的大量研究足以顯示該問題很難，但是還有一些形式化的結果證明為什麼該問題可能很難解決。

最常參照的結果之一是設計神諭。假想你有部魔法機器可以解決單一問題，例如「判定某數是否質數」，這魔法機器可以瞬間解決這問題。我們的新問題是，若我們獲允許任意利用這機器，是否存在我們可以在多項式時間內驗證但無法在多項式時間內解決的問題？結果是，依賴於機器能解決的問題，**P**=**NP** 和 **P**≠**NP** 二者都可以證明。這個結論帶來的後果是，任何可以通過修改神諭來證明該機器的存在性的結果不能解決問題。不幸的是，幾乎所有經典的方法和大部分已知的方法可以這樣修改（我們稱它們在**相對化**）。

如果這還不算太糟的話，1993 年 Razborov 和 Rudich 證明的一個結果表明，給定一個特定的可信的假設，在某種意義下「自然」的證明不能解決 **P**=**NP** 問題。[2]（頁面存檔備份，存於網際網路檔案館）這表明一些現在似乎最有希望的方法不太可能成功。隨著更多這類定理得到證明，該定理的可能證明方法有越來越多的陷阱要規避。

這實際上也是為什麼 **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！」。

康奈爾大學的 Hubert Chen 博士提供了這個玩笑式的 P 不等於 NP 的證明：

> 反證法。設 P=NP。令 y 為一個 P=NP 的證明。證明 y 可以用一個合格的電腦科學家在多項式時間內驗證，我們認定這樣的科學家的存在性為真，但因為 P=NP，該證明 y 可在多項式時間內由這樣的科學家發現，但是這樣的發現還沒有發生（雖然這樣的科學家試圖發現這樣的一個證明），我們得到矛盾。
> 
> 

## 註釋

## 參考文獻

## 延伸閱讀

## 外部連結

* 未來數學家的挑戰（P 與 NP 的簡介，清楚明瞭）（頁面存檔備份，存於網際網路檔案館）（繁體中文）
* The Clay Math Institute Millennium Prize Problems
* 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（頁面存檔備份，存於網際網路檔案館）

## 參見

* P (複雜度)
* NP (複雜度)
* NP 完全
* 未解決數學問題
* NP-complete 問題列表
* 幾乎完備（Almost complete）問題與弱完備（weakly complete）問題
* ASR-complete
* Ladner 理論
* NP 困難