P/NP問題

P/NP問題（P versus NP problem）是理論電腦科學中核心的未解問題。通俗而言，它探討的是：如果一個問題的答案能夠被快速驗證，那麼這個問題本身是否也能被快速求解？

具體而言，這裡的「快速」指的是存在一種演算法，可以在與輸入規模呈多項式時間的關係內計算出結果（這與耗時極長的指數時間等概念相對）。換言之，完成任務所需的時間上限是輸入規模的多項式函數。那些能在多項式時間內被演算法解決的判定問題類別，被稱為「P」或「P類問題」。相反，對於某些問題，目前人類還沒有找到快速求解的方法，但如果有人提供一個候選解，我們卻能快速驗證它是否正確。這類解能在多項式時間內被驗證的問題類別，被稱為「NP」（即「非確定性多項式時間」）。

P/NP問題的答案將直接決定：那些解法容易被驗證的問題，是否也必然容易被求解。如果結果如目前學術界普遍猜想的那樣（即 $\mathsf{P} \neq \mathsf{NP}$），那就意味著NP類別中存在一些問題，它們的解極易驗證，但想要直接計算出解卻極其困難（無法在多項式時間內求解）。

該猜想被公認為電腦科學領域最重要的未解之謎。它不僅是計算理論的基石，而且無論其最終證明結果如何，都必將對數學、密碼學、演算法研究、人工智慧、博弈論、多媒體處理、哲學以及經濟學等眾多領域產生深遠影響。該問題也是克雷數學研究所評選出的七大千禧年大獎難題之一，首個提供嚴謹證明的人將獲得100萬美元的獎金。

## 示例

以一個判定問題為例：給定一個 $n^2 \times n^2$ 的不完整數獨棋盤，是否存在至少一種合法的填法，使得每行、每列以及每個 $n \times n$ 的宮格都恰好包含從 1 到 $n^2$ 的所有整數？如果有人提供了一個填好的候選解，我們能相對快速地驗證這個廣義數獨的答案是否正確。然而，目前學術界尚不清楚，是否存在一種能夠在多項式時間內運行的演算法，可以直接推算盤面並準確回答「是否有解」。因此，廣義數獨問題屬於NP類（解的正確性可被快速驗證），但它究竟是否屬於P類（能否被快速推算求解），目前仍是未知數。（這裡討論廣義數獨很有必要，因為對於我們日常見到的標準 9×9 數獨，其可能的組合只有有限種，電腦完全能在短時間內通過查表找到答案，因此固定規模下的數獨實際上屬於P類。）

## 歷史

P/NP問題的嚴格定義最早由史蒂芬·庫克在1971年的開創性論文《定理證明程序的複雜性》（The complexity of theorem proving procedures）中提出，數學家列昂尼德·列文也在1973年獨立提出了完全相同的定理。

儘管P/NP問題直到1971年才被賦予正式的學術定義，但人們對潛藏其背後的底層邏輯早有察覺。1955年，著名數學家約翰·納什在寫給美國國家安全局的一封信中推測，破解一個足夠複雜的密碼所需的時間，將隨著密鑰長度的增加呈指數級增長。如果納什的推測成立（儘管他本人亦持懷疑態度），這就等同於如今所說的 $\mathsf{P} \neq \mathsf{NP}$ 猜想，因為嘗試性的密鑰是能夠在多項式時間內被驗證的。1956年，庫爾特·哥德爾在寫給約翰·馮·諾伊曼的一封著名信件中，也詢問了定理證明過程（如今已知為反NP完全問題）是否能在二次時間或線性時間內解決。他假定，如果能在多項式時間內解決，那麼數學證明的過程就能被自動化。

## 背景

複雜性類 P與NP之間的關係，是計算複雜性理論（計算理論的一個重要分支）的核心研究對象。該理論主要研究在計算過程中，解決給定問題需要耗費多少資源。最關注的兩種資源是「時間」（計算步驟數）和「空間」（記憶體消耗量）。

為了精確進行這種分析，我們需要引入理論模型來計算機器耗費的時間。通常，這些模型會假定電腦是確定性計算的（即給定當前狀態和輸入，電腦只能採取唯一的一種操作），並且是順序的（只能逐條執行操作）。

在這一理論框架下，P類包含的所有判定問題都可以由一台確定性順序機器在輸入規模的多項式時間內解答；而NP類則包含所有如果在給定正確提示的情況下，能夠於多項式時間內順利驗證肯定解的判定問題。這等價於說，NP類問題是能夠在一台非確定性圖靈機上於多項式時間內找到解的問題。顯然，P類是包含於NP類之中的（$\mathsf{P} \subseteq \mathsf{NP}$）。可以說，理論電腦科學界最大的未解之謎，就是這兩個複雜性類別之間的關係：

P等於NP嗎？

自2001年起，學者威廉·加薩奇針對 $\mathsf{P} = \mathsf{NP}$ 及其相關議題，向電腦科學界的研究人員進行了三次問卷調查。認為 $\mathsf{P} \neq \mathsf{NP}$ 的受訪者比例在2001年占61%，The polls were conducted in 2001, 2011, and 2018 but published in 2002, 2012, and 2019 respectively. 到了2011年上升至83%，而在2018年則達到了88%（這三次調查分別收到了100份、151份和124份回復）。當把統計範圍僅限定為領域內的頂級專家時，2018年高達99%的受訪者認為 $\mathsf{P} \neq \mathsf{NP}$。當然，民意調查並不能在數學上證明 $\mathsf{P} = \mathsf{NP}$ 是否成立；正如加薩奇本人所言：「這並沒有讓我們在解決問題上邁進哪怕一步，也沒有告訴我們它何時會被解決。這僅僅是一份關於我們這個時代主觀意見的客觀報告。」

## NP完全性

<image>

「NP完全」（NP-complete）概念在探索 P/NP 問題時發揮了關鍵作用。一個問題被稱為NP完全問題，意味著所有其他NP問題都能在多項式時間內歸約（轉化為）該問題，且它自身的解也能在多項式時間內被驗證。通俗來講，NP完全問題是所有NP問題中最困難的一類，它至少與任何其他NP問題一樣具有挑戰性。

而NP困難問題是指那些難度至少與NP問題相當的難題；即，所有NP問題都能夠在多項式時間內歸約到它們。需要注意的是，NP困難問題自身不一定屬於NP；換言之，它們的解不一定能在多項式時間內被驗證。

舉個例子，由著名的庫克-列文定理可知，布爾可滿足性問題（SAT）是一個典型的NP完全問題。因此，NP類別中任何問題的任何實例，都可以在多項式時間內機械地轉化為布爾可滿足性問題。只要能證明任何一個NP完全問題屬於P類（即找到了多項式時間的解法），就能直接推導出 $\mathsf{P} = \mathsf{NP}$。然而，許多重要的現實問題已被證明是NP完全的，且至今尚未找到能快速求解它們的演算法。

僅看定義，去相信「NP完全問題真的存在」似乎有些反直覺；但實際上，我們可以輕易構造出一個微不足道的NP完全問題：給定一台保證在多項式時間內停機的圖靈機 $M$，是否存在一個多項式大小的輸入能讓 $M$ 接受？它屬於NP類，因為（給定輸入後）我們只需運行一遍 $M$，就能輕鬆檢查 $M$ 是否接受；同時它也是NP完全的，因為任何NP問題實例的驗證器，都可以編碼為一台以「待驗證的解」作為輸入的多項式時間機器 $M$。該實例是否有解，完全等價於是否存在能讓 $M$ 接受的有效輸入。

歷史上第一個被證明為自然的NP完全問題正是布爾可滿足性問題（SAT）。如前所述，這也是庫克-列文定理的意義所在；其證明過程包含了大量與圖靈機底層機制及NP嚴格定義相關的技術細節。然而，在SAT問題被確認為NP完全之後，學者們利用歸約證明這種更為簡便的方法，通過逐步推導證明了許多其他問題同樣是NP完全的，其中就包括前文提到的數獨遊戲。在這種歸約邏輯下：如果在多項式時間內能解出廣義數獨，那麼這套解法就能被直接套用來在多項式時間內完成拉丁方陣。拉丁方陣的高效解法又能進一步為將三分圖劃分為三角形的問題提供解法，這又能解決一種被稱為3-SAT的特殊SAT問題，並最終解決一般化的布爾可滿足性問題。綜上所述，廣義數獨的多項式時間解法通過一系列歸約，能直接引出SAT問題的多項式時間解法，而SAT的解法又能用來解決所有其他NP問題。正是藉助這種轉換機制，一大批表面上看似毫無關聯的問題被相互串聯了起來。

## 更難的問題

儘管學術界至今無法確定P是否等於NP，但在P類之外，確實存在更為困難的問題。正如P類是根據多項式運行時間界定的一樣，EXPTIME類包含所有運行時間呈指數級增長的判定問題。換言之，EXPTIME中的任何問題都可以在由確定性圖靈機耗費大O符號 $O(2^{p(n)})$ 的時間內解決，其中 $p(n)$ 是 $n$ 的多項式函數。如果一個判定問題本身屬於EXPTIME，並且EXPTIME中的所有問題都能通過多項式時間歸約轉化為該問題，那麼它被稱為EXPTIME完全。目前已證實存在許多EXPTIME完全問題。因為數學上已經證明了 $\mathsf{P} \neq \mathsf{EXPTIME}$，這些問題被明確排除在P類之外，求解它們必然需要耗費超過多項式時間的資源。事實上，時間層次定理已經嚴格證明，這類問題絕不可能在遠低於指數級的時間內得到解決。現實中的例子包括：在 $N \times N$ 的棋盤上推演出完美的西洋棋必勝策略，以及其他各類複雜棋盤遊戲的類似問題。

去判定普萊斯伯格算術中語句的真偽，需要耗費更長的時間。費雪和拉賓在1974年給出了嚴謹證明：任何用於判斷長度為 $n$ 的普萊斯伯格語句真偽的演算法，其運行時間都至少會達到 $2^{2^{cn}}$（其中 $c$ 為某個常數）。因此，這類問題被證明需要超過指數級的運行時間。而比這還要艱難的，則是那些邏輯上無法被演算法解答的不可判定問題，例如著名的停機問題。它們無法由任何通用演算法徹底解決；也就是說，對於任何特定演算法，必定存在至少一個輸入使其無法輸出正確答案：它要麼輸出錯誤結果，要麼陷入死循環永遠無法停止。

除了討論「是否有解」的判定問題，複雜性理論還關注其他計算類型。其中一類由計數問題組成，被稱為#P類別：既然NP探討的是「問題是否有解？」，那麼相對應的#P探討的則是「問題究竟有多少個解？」。顯然，如果算出的解數大於零，就立刻表明至少存在一個解，因此#P問題的難度門檻絕對不低於其對應的NP問題。令人驚訝的是，某些看似極難的#P問題，其對應的判定問題卻相對容易（例如可以在線性時間內求解的P問題）。對於這類問題，判斷「是否有解」相對簡單，但確切算出「有多少個解」卻極其困難。這類問題大部分屬於#P完全，也就是#P類別中的最高難度問題，只要找到針對其中任意一個難題的多項式時間解法，就能直接為所有其他#P問題提供多項式解法。

## NP中已知既不屬於P也不屬於NP完全的問題

1975年，學者理察·拉德納提出了一個重要證明：如果 $\mathsf{P} \neq \mathsf{NP}$，那麼在NP的大框架內，必定存在既不屬於P、也不屬於NP完全的問題。這類問題被稱為「NP中介問題」。包括圖同構問題、離散對數問題以及整數分解問題等，都被視為NP中介問題的典型代表。它們是極少數尚無定論、難以直接判定其究竟屬於P還是NP完全的NP難題。

圖同構問題旨在判定兩個有限的圖之間是否存在圖同構關係。在複雜性理論界，圖同構問題究竟歸屬於P、NP完全還是NP中介，一直是一個備受矚目的未解懸案。雖然最終答案仍未確定，但主流觀點普遍認為該問題至少不應當是NP完全的。如果圖同構真的是NP完全問題，那麼根據理論推導，整個多項式時間層次體系將會坍縮到它的第二層。由於學術界普遍認為多項式層次絕不會坍縮到有限層，因此更傾向於認為圖同構不是NP完全問題。由拉茲洛·巴拜提出的求解該問題的目前已知最佳演算法，能夠在准多項式時間內運行完畢。

整數分解問題旨在求出一個給定整數的精準素數分解。將其轉化為判定問題即為：判斷輸入的數字是否具有小於某個特定值 $k$ 的素因子。時至今日，人類尚未找到任何已知的高效整數分解演算法，而正是基於這種難以破解的數學特性，構築了諸如RSA演算法等現代密碼系統的安全基石。整數分解問題同時歸屬於NP與co-NP（甚至屬於更為特殊的UP和co-UP）。如果能證明該問題是NP完全的，那麼多項式時間層次將徹底坍縮到第一層（即 $\mathsf{NP} = \mathsf{co-NP}$）。目前已知針對大整數分解最高效的經典演算法是普通數域篩選法，它在分解一個長達 $n$ 位的整數時，所耗費的期望時間為：

$$O\left (\exp \left ( \left (\tfrac{64n}{9} \log(2) \right )^{\frac{1}{3}} \left ( \log(n\log(2)) \right )^{\frac{2}{3}} \right) \right )$$

在量子計算領域，針對該問題的最佳已知量子演算法是極具革命性的秀爾演算法，它能夠在多項式時間內運行，儘管這一壯舉尚未完全明確該問題在非量子複雜性理論中具體所處的類別坐標。

## P類與「簡單」問題的對比

<image>

前文的所有探討都建立在一個普遍的假設之上：即認為P類代表「計算簡單」，而「不在P中」代表「計算困難」。在複雜性理論中，這一假設被稱為「科巴姆論題」。儘管這是領域內的共識，但在現實應用中，它同樣存在一些不容忽視的局限性。

首先，從工程實踐的角度來看，這個理論可能會脫節。一個在理論上被證明屬於多項式時間的演算法，可能攜帶著巨大的常數因子或龐大的指數項，導致它在實際應用中難以運行。例如，判定一個圖 $G$ 是否包含特定的圖 $H$ 作為其圖子式，在理論上能夠以 $O(n^2)$ 的運行時間解決，其中的 $n$ 代表圖 $G$ 中的頂點總數。然而，大O符號在這個 $O(n^2)$ 背後隱藏了一個極大的常數，該常數對 $H$ 呈現多重指數級的依賴。這個常數甚至比 $2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2)))$ （採用高德納箭號表示法）還要巨大，其中的 $h$ 是 $H$ 中的頂點數。

另一方面，就算某個問題被定性為NP完全，甚至即便 $\mathsf{P} \neq \mathsf{NP}$ 成立，在實踐中依然可能有應對該難題的有效手段。許多典型的NP完全問題，例如背包問題、旅行推銷員問題以及布爾可滿足性問題等，目前都已擁有非常成熟的現成演算法，它們能夠以令人滿意的速度，在合理時間內找到許多現實世界複雜實例的最優解。這些演算法在經驗測試中展現出的平均情況複雜性（耗時與問題規模的對比）往往相對較低。一個例子是線性規劃中的單純形法，它在現實工業應用中表現得非常優異；儘管在極端的理論最壞情況下，它具有指數級的高時間複雜度，但它在絕大部分日常運算中的表現，並不遜色於目前任何已知的多項式時間演算法。

此外，P與NP的定義完全根植於傳統的經典圖靈機模型。如果我們把目光投向不符合該模型的其他前沿計算類型，例如量子計算和隨機演算法，整個複雜性理論體系可能會呈現出完全不同的風貌。

## 猜想 P ≠ NP 或 P = NP 的理由

庫克在《P與NP問題》（The P Versus NP Problem）一文中，將該問題精煉地表述為：「P = NP 嗎？」根據歷次民意調查結果，絕大多數電腦科學家傾向於認為 $\mathsf{P} \neq \mathsf{NP}$。支撐這一主流信念的一個重要理由是：在大量學者對這些問題進行了長達數十年的深入研究之後，時至今日，依然沒有任何一個人能夠為3000多個已知的重要NP完全問題（參見NP完全問題列表）中的任何一個找到多項式時間演算法。事實上，早在NP完全性概念被正式提出之前，人們就已經在尋找這些演算法了（例如最先被發現的卡普的21個NP完全問題，在它們被證明為NP完全時，就已經全是當時困擾學界已久的難題）。此外，如果未來某一天得出 $\mathsf{P} = \mathsf{NP}$ 的結論，將導致許多目前在學界被認為極度不成立的結論隨之成立，例如 $\mathsf{NP} = \mathsf{co-NP}$ 以及 $\mathsf{P} = \mathsf{PH}$。

從人類直覺的層面來看，有一種頗具說服力的觀點認為：世界上確實存在著那些「解答困難，但驗證容易」的問題，這契合我們在現實生活中的真實經驗。

如果 $\mathsf{P} = \mathsf{NP}$，那麼這個世界的運轉邏輯將與我們往常假設的截然不同。所謂的「創造性飛躍」將不再具有任何特殊價值，而在費盡心思解決一個難題與答案被找到後一眼識別出它之間，也不再存在根本的智力鴻溝。

另一方面，也有少數研究人員提出不同觀點，認為絕對認定 $\mathsf{P} \neq \mathsf{NP}$ 可能缺乏嚴謹的求證精神，研究人員同樣應當探索 $\mathsf{P} = \mathsf{NP}$ 的可能性。例如，在2002年就有人發表了如下聲明：

支持 $\mathsf{P} \neq \mathsf{NP}$ 的最主要論點，無非是在演算法窮舉搜索領域完全缺乏任何根本性的進展。但在我看來，這是一個不夠充分的論點。演算法的探索空間是極其浩瀚的，而我們人類目前僅僅處於探索的起步階段。... 費馬大定理最終的解決歷程也生動地向我們表明，某些看似簡單的問題，往往只能通過深奧的理論才能得以破解。

過度堅持一種未經證實的猜測，不是規劃嚴謹學術研究的好指引。我們理應對每一個未解之謎嘗試從正反兩個方向同時入手。盲目的偏見已經導致了歷史上許多傑出的數學家在解決著名問題時遭遇挫折——即便他們有時已經掌握了推導所需的所有工具，但僅僅因為問題的真實答案與他們的預期背道而馳，最終依然未能成功。

### DLIN與NLIN

如果在P和NP的嚴格定義中，我們用「多帶圖靈機上的線性時間」替換「多項式時間」這一條件，就會得到DLIN和NLIN這兩個全新的複雜性類別。

目前在數學上已經明確證實：DLIN ≠ NLIN。

## 破解該問題的影響

這個問題之所以能吸引全球學者的關注，核心原因之一就在於它可能帶來的巨大影響。無論最終朝著哪個方向被解決，都將帶來理論電腦科學的重大飛躍，甚至可能改變現實社會的應用版圖。

### P = NP

如果真的證明了 $\mathsf{P} = \mathsf{NP}$，這將引發巨大的實際影響——前提是該證明能夠順勢牽引出一種求解某些高價值NP問題的高效演算法。由於各類NP完全問題在現代科學的諸多領域都是基礎性問題，這一證明帶來的正負面潛在影響將是難以估量的。

然而，同樣可能發生的情況是，即便給出了證明，它也無法為NP完全問題帶來任何在現實中可運行的實用演算法。因為P/NP問題的原始公式設定並沒有要求作為運行時間上限的那個「多項式」必須很小，或者必須被明確計算出來。一個純粹的非構造性證明可能僅僅在數學邏輯上宣告了「存在這樣一個解」，但既不提供獲取它的演算法代碼，也無法給出一個具體的算力消耗界限。退一步說，即使該證明是嚴謹的構造性證明，清晰展現了多項式界限和算法執行細節，但如果該多項式的階數極大（例如需要 $O(n^{100})$ 的時間），那麼該演算法在當前的物理世界中依然缺乏實際應用價值。在這種情況下，這個證明最初將僅僅限於理論探討；不過，得知多項式時間解法在理論上可行，無疑會極大激勵研究人員去尋找更好的實際實現路徑。

一旦拿出了極具實用價值的 $\mathsf{P} = \mathsf{NP}$ 解答，整個現代密碼學體系可能面臨失效風險，因為該領域的運作根基，恰恰建立在「某些計算問題屬於無法在多項式時間內求解的困難問題」這一信念之上。設想一下，如果能為一個像3-SAT這樣的NP完全問題找到一種高效解法

$O(N^2)$

$\Omega(N^4)$

那麼現存於世的大多數防線將被擊穿，這其中包括：

- 現有公開密鑰加密演算法的主流商業實現，這是支撐全球網際網路通信和金融交易的安全基礎。
- 用於加密通信數據本身的對稱密鑰加密技術，例如高級加密標準（AES）或傳統的三重資料加密演演算法（3DES）。
- 密碼散列函數，它是所有區塊鏈加密貨幣（如著名的比特幣）運轉的基礎，也被廣泛用於驗證全球軟體更新包的真實性與防篡改。對於這些應用而言，逆向尋找一個能散列出給定特徵值的原始數據，必須被設計得極其困難。可一旦 $\mathsf{P} = \mathsf{NP}$，通過向SAT問題進行簡單的歸約，現有的加密體系就有可能在多項式時間內被破解。

為了應對危機，全球的基礎網路系統必須被迫進行全面升級，或者切換為那些完全不依賴 $\mathsf{P} \neq \mathsf{NP}$ 假設的資訊理論安全方案。

當然，將目前在數學上難以處理的問題變得易於處理，也將為社會帶來科技紅利。例如，運籌學中的大量核心優化問題都是NP完全的，如負責調度的各類整數規劃，以及旅行推銷員問題。一旦為這些問題配備了高效解法，將極大降低運輸與製造成本。許多其他重大的科學問題，比如醫學界蛋白質結構預測中的某些關鍵摺疊問題，同樣是NP完全的；解決它們將促進新藥研發和生物技術的發展。

與高效求解NP難題帶來的影響相比，上述行業變化或許只是一部分。哥德爾在早期關於計算複雜性的思考中就曾指出：如果世上真的存在一種能夠解決任何邏輯問題的機械方法，那將極大地改變數學家的工作方式：

如果真的存在一台運算滿足 $\varphi(n) \sim k \cdot n$（甚至哪怕滿足 $\sim k \cdot n^2$）的機器，那必將引發極其重大的後果。這表明，儘管判定問題具有不可判定性，但數學家在回答「是或否」這類定理真偽問題上的勞作，都可以被機器取代。畢竟，我們只需要把自然數 $n$ 設置得足夠大，如果連這台機器都無法給出結果，那麼人類再花更長時間去思考這個問題，也就沒有實際意義了。

同樣地，史蒂芬·庫克也描繪了這樣一幅圖景：

... 它將賦予電腦極大的能力，去自動搜尋任何存在合理長度證明的定理的形式化證明。因為形式化的證明在多項式時間內是極容易被機器識別和驗證的。這必將徹底改寫數學體系的形態。一旦機器擁有了這種能力，所有懸而未決的克雷數學研究所千禧年大獎難題都可能被迅速解決。

幾千年來，研究型數學家致力於證明各種晦澀的定理。有些證明在問題提出後，往往需要耗費數十年的時間才能被攻克——例如，費馬大定理就花了三百多年的時間才得以徹底證明。如果真的存在一種終極演算法，只要某個定理存在「合理」長度的證明，就必然能輕易地找到它，那麼這方面的學術研究將發生根本性改變。

電腦科學家高德納曾表示，他傾向於相信 $\mathsf{P} = \mathsf{NP}$，但他對這一潛在證明可能帶來的實際影響抱保守態度：

... 假設存在一個數字 $M$，它極其龐大——比如 $10 \uparrow\uparrow\uparrow\uparrow 3$——那麼在這個範圍內，必然存在著海量的潛在演算法，它們可以對 $n$ 個給定的比特執行 $n^M$ 次運算。從機率學上講，你很難相信在如此海量的潛在演算法中，完全不存在任何有效的演算法。

然而，我不認為即使有人證明了 $\mathsf{P} = \mathsf{NP}$，能給實際的程序編寫帶來立竿見影的幫助。因為這種證明，幾乎肯定是不提供具體構造方法的非構造性證明。

<image>

### P ≠ NP

如果最終被證明出的是 $\mathsf{P} \neq \mathsf{NP}$，雖然它否定了通過單一演算法解決所有難題的設想，缺乏 $\mathsf{P} = \mathsf{NP}$ 證明所能帶來的現實計算紅利，但它依然代表了計算複雜性理論認知上的進步，並為未來的研究指明方向。它將清楚地告示人們：許多研究了半個世紀的常見難題，根本不可能存在完美的高效通用解法。這能讓研究人員及時調整方向，把精力轉移到尋找局部最優解、近似解或解決其他問題上。事實上，正是由於當今學術界普遍認為 $\mathsf{P} \neq \mathsf{NP}$，這種科研重心的轉移早已在各行各業發生。

然而，$\mathsf{P} \neq \mathsf{NP}$ 這一結論，依然無法解答關於NP內部那些棘手問題的平均情況複雜性疑慮。舉個例子：SAT問題在遇到極端惡劣的最壞情況時，確實可能需要耗費指數級的時間來破解；但在真實工程中，如果我們隨機抽取一些SAT的常規實例，它們往往能夠被高效求解。學者羅素·因帕利亞佐曾構建過一個思想實驗，描述了由「平均情況複雜性問題」不同可能解答所催生出的五個假設世界。這些世界從理想的「演算法烏托邦」（Algorithmica，在這個世界裡 $\mathsf{P} = \mathsf{NP}$，任何實例都能被輕鬆求解），一路滑向複雜的「密碼狂熱世界」（Cryptomania，在這個世界裡 $\mathsf{P} \neq \mathsf{NP}$，並且人為製造困難實例相對容易）。在這兩極之間，還存在三種過渡性世界，映射了計算難度的各種情況。在他的論文中，那個雖然 $\mathsf{P} \neq \mathsf{NP}$ 成立，但幾乎所有NP問題在平均情況下都會變得容易處理的世界，被命名為「啟發式世界」（Heuristica）。2009年，在普林斯頓大學的一場研討會上，學者們專門圍繞這五個世界的理論現狀展開了探討。

## 證明難度的相關結論

儘管 P/NP 問題自身帶有巨額賞金，並且吸引了全球眾多學者的持續研究，但它至今依然懸而未決。然而，全人類為了解決這個問題所付出的巨大努力，催生了一大批數學分析新技術的誕生。特別需要強調的是，與 P/NP 問題相關的一些重要科研成果，恰恰證明了：人類目前所掌握的任何已知論證技術，都不足以回答這個問題。這宣告了想要解決這個問題，就必須開闢全新的技術路徑。

作為該問題難度之高的另一佐證，可以審視目前計算複雜性理論中幾乎所有已知的高級證明技術。它們全都被歸入以下幾種分類，且無一例外，全都在證明 $\mathsf{P} \neq \mathsf{NP}$ 時遭遇壁壘：

分類｜定義

相對化證明｜在理論模型中構建這樣一個特定的世界：允許每一個演算法向某個被稱為預言機的子程序發起詢問（它能在常數時間內立刻解答一組固定範圍內的難題），並且該預言機的運行時間不計入演算法自身的運行時間內。大多數傳統的證明手法（尤其是經典的推導證明），在這個設定中都能順暢應用，無論預言機背後執行什麼操作。這類高度依賴該設定的證明手法被稱為相對化的。1975年，貝克（Baker）、吉爾（Gill）和羅伯特·索洛維聯手證明了一個重要結論：對於某些特定的預言機，存在 $\mathsf{P} = \mathsf{NP}$ 的情況；而換用另一些預言機，結果又變成 $\mathsf{P} \neq \mathsf{NP}$。由於相對化證明體系只能證明那些對所有可能預言機都絕對成立的普適陳述，這就註定了這種受限的技術路徑無法解決 P/NP 問題。

自然證明｜1993年，學者亞歷山大·拉茲波羅夫和史蒂芬·魯迪奇為電路複雜性下界定義了一大類通用的證明技術框架，將其命名為自然證明。當時，所有已知的電路下界證明無一例外都是基於這種路線的，而破解電路複雜性一直被學術界視為有望解決 $\mathsf{P} = \mathsf{NP}$ 的最可能突破口。然而，拉茲波羅夫和魯迪奇隨後證明：只要存在哪怕一種單向函數，那麼對於這種「自然證明」方法而言，P和NP就是難以區分的。雖然至今單向函數在數學上的存在性尚未被完全證實，但絕大多數數學家都相信它們存在，並且從邏輯上講，想要證明單向函數存在，本身就是一個比證明 $\mathsf{P} \neq \mathsf{NP}$ 更強有力的斷言。因此，指望單憑傳統的自然證明去解決 $\mathsf{P} = \mathsf{NP}$ 是極不現實的。

代數化證明｜在得出上述結論後，新的非相對化證明技術出現，並被成功用於跨界證明 IP = PSPACE 這一重要定理。然而到了2008年，學者斯科特·阿倫森和阿維·威格森證明了：在 IP = PSPACE 證明中使用的核心技術（被稱為算術化技術），在面對 $\mathsf{P} = \mathsf{NP}$ 時同樣無能為力。算術化技術的精髓在於能夠把複雜的演算法運算巧妙轉化為純粹的代數與算術符號。在 IP = PSPACE 的證明中，他們將演算法的黑盒和底層布爾電路轉化為了代數問題。正如前文所述，殘酷的事實表明，這種代數化的方法在直面 P/NP 及其他深度的時間複雜度難題上，同樣受到了限制。

上述理論壁壘從側面說明了為什麼「NP完全問題」如此具有價值：假使某位學者能夠為任意一個NP完全問題找到多項式時間演算法，這便能以一種無視上述理論壁壘阻礙的突破性方式，一勞永逸地解決 $\mathsf{P} = \mathsf{NP}$ 問題。

正是這些看似難以逾越的理論壁壘，促使一部分電腦科學家提出一個大膽猜想：P/NP問題本質上可能完全獨立於諸如ZFC這樣的標準數學公理系統。如果這一結論最終被證實，意味著兩種可能：要麼 $\mathsf{P} \neq \mathsf{NP}$ 成立，但這在ZFC系統中無法被證明；要麼 $\mathsf{P} = \mathsf{NP}$，但即便找到了高效演算法，在ZFC系統內也永遠無法給出嚴謹的數學證明去背書這些演算法的正確性。值得注意的是，如果退讓一步，引入遠比擴展整數算術的皮亞諾公理弱的假設，該問題仍然具有不可判定性，那麼根據逆向推導，所有龐大的NP問題群體都必然會存在某種接近多項式時間的極其高效的演算法。既然絕大多數理論學家都相信許多NP問題不存在如此高效的演算法，那麼妄圖利用現有技術去證明「獨立性」，同樣是一條走不通的路。這表明，想要用人類目前掌握的技術證明該問題獨立於PA或ZFC系統，其難度與證明「所有NP問題都存在高效演算法」一樣是不切實際的。

## 邏輯表述

得益於在描述複雜性領域的突破，P/NP問題能夠被重新表述為對某些特定形式的邏輯陳述類別的探討。

考慮所有帶有包含線性序關係在內的某個固定簽名的有限結構的語言集合。歸屬於P類的語言，實際上都可以通過在傳統的一階邏輯基礎上，加上特定的最小不動點組合子來進行表達。只要這個簽名系統中，除了序關係外還包含至少一個謂詞或函數，使得電腦在存儲此類有限結構時所占用的空間，受限於該結構中元素數量的多項式規模，這套理論就刻畫了P類的特徵。

NP類也能被類似地映射出來。它實質上可以用存在性二階邏輯（這裡特指一種受限的、排除了針對關係、函數及子集的全稱量化的二階邏輯變體）來表達的語言集合。而那些屬於多項式時間層次PH的語言，則對應於完整的二階邏輯。經過這一理論轉換，「P是否僅僅是NP的一個真子集」這一問題，就可以表述為：「針對具有非平凡簽名的有限線性有序結構，存在性二階邏輯是否具備描述『一階邏輯搭配最小不動點組合子』所無法觸及的語言的能力？」。甚至前面這個描述中的「存在性」這三個字都可以被省略，因為若且唯若 $\mathsf{P} = \mathsf{PH}$ 成立時，$\mathsf{P} = \mathsf{NP}$ 才成立。

## 多項式時間演算法

目前沒有任何已知針對NP完全問題的演算法，能夠在現實環境的多項式時間內運行完畢。然而，對於某些極度難纏的NP完全問題，理論上確實存在已知演算法，且如果 $\mathsf{P} = \mathsf{NP}$ 成立，該演算法在處理肯定的輸入實例時將會快速運行（儘管該演算法中包含的常數項極其龐大，導致它在任何物理電腦上都缺乏實用價值）。由於這些演算法在處理否定的實例時，運行耗時依然會大幅突破多項式時間限制，因此它們仍不符合「絕對多項式時間」的定義。下面這個由學者列昂尼德·列文提出的特殊演算法，正是這樣一個極端的例子。它能夠接受NP完全語言子集和問題（SUBSET-SUM）。若且唯若 $\mathsf{P} = \mathsf{NP}$ 成為現實時，該演算法在處理屬於SUBSET-SUM的輸入時，才會在多項式時間內運行完畢：

```text
 // 接受NP完全语言SUBSET-SUM的伪代码算法。
 //
 // 当且仅当 P = NP 成立时，这是一个多项式时间算法。
 //
 // 这里“多项式时间”的真实含义是：当问题的答案为“是”时，它会在多项式时间内输出“是”。
 // 而当答案为“否”时，它会陷入死循环，永远运行下去。
 //
 // 输入：S = 一个有限的整数集合
 // 输出：如果 S 中存在任何一个子集的元素之和恰好为 0，则输出“是”。
 // 否则程序将永远运行，不产生任何输出。
 // 注意：“程序 M”是通过暴力枚举得来的：
 // 将整数 M 直接转换为二进制，并将其强行视为一段可执行程序。
 // 理论上所有可能存在的程序都能以此方式生成，尽管大部分
 // 在第一步就会因为语法错误而立刻崩溃。
 FOR K = 1...∞
   FOR M = 1...K
     以 S 为输入，强行运行“程序 M” K 个计算步
     IF 该程序输出一个由不同整数组成的列表
       AND 这些整数全都毫无遗漏地包含在原集合 S 中
       AND 这些整数的累加之和恰好为 0
     THEN
       OUTPUT "是" 并触发 HALT（停机指令）
```

這絕對是一個唯有當 $\mathsf{P} = \mathsf{NP}$ 降臨時，才能夠在多項式時間內成功接受NP完全語言的特殊演算法。在這裡對「接受」一詞的定義非常寬容：它意味著演算法在多項式時間內明確給出「是」的結果，但當答案為「否」時，允許其無休止地運行（這種演算法在理論上也被稱作半演算法）。

即使 $\mathsf{P} = \mathsf{NP}$，該演算法也因為其暴力的窮舉邏輯而顯得極度不切實際。試想一下，如果能夠在一套正常邏輯框架下，在多項式時間內解決SUBSET-SUM問題的最短且最優程序代碼長度僅為 $b$ 個比特，那麼上述演算法在盲目嘗試得出正確答案之前，至少需要嘗試執行高達 $2^b - 1$ 個無效程序。

## 形式化定義

### P 和 NP

在計算理論的嚴謹框架下，一個標準的判定問題指的是這樣一個邏輯設定：它接收由底層字母表 Σ 構建出的特定字串 $w$ 作為唯一輸入，並輸出「是」或「否」。如果存在一種演算法（可以具象化為一台絕對理性的圖靈機，或者一段占用必要記憶體的電腦程式），能夠在最多 $cn^k$ 步的算力消耗內，針對任何長度為 $n$ 的輸入字串可靠地產生正確答案（其中 $k$ 和 $c$ 是兩個恆定不變的常數），那麼我們在理論上就宣稱該問題可以在多項式時間內被解決，並將其歸入類別P。用數學語言形式化地表述，P 類就是那些能夠被確定性多項式時間圖靈機判定的語言集合。即。

$$\mathsf{P} = \{ L : L=L(M) \text{ 对某个确定性多项式时间图灵机 } M \}$$

其中

$$L(M) = \{ w\in\Sigma^{*}: M \text{ 接受 } w \}$$

並且，這裡所謂的「確定性多項式時間圖靈機」，指的是必須滿足以下兩條規則的確定性圖靈機 $M$：

- $M$ 在面對所有可能的輸入 $w$ 時，都必須保證最終停機，並且
- 必然存在某個自然數 $k \in N$，使得 $T_M(n)\in O(n^k)$ 成立，這裡的 $O$ 指代大O符號的正式定義，並且

$$T_M(n) = \max\{ t_M(w) : w\in\Sigma^{*}, |w| = n \}$$

$$t_M(w) = M\text{ 在处理输入 }w\text{ 上直至停机所必须耗费的总步数。}$$

NP類的定義也可以用極為相似的方式推導，只需引入非確定性概念即可（這是理論界最傳統的定義法）。然而，現代學術界更青睞採用證書與驗證器概念。形式化地講，NP類是定義在有限基礎字母表上的、並且擁有一個能受控在多項式時間內運行完畢的驗證器的語言集合。關於「驗證器」的定義如下：

設 $L$ 是定義在有限字母表 Σ 上的語言集。

$L \in \mathsf{NP}$ 能夠成立的充要條件是：存在一個二元關係 $R\subset\Sigma^{*}\times\Sigma^{*}$ 以及一個正整數 $k$，滿足以下兩個條件：

- 對所有 $x\in\Sigma^{*}$，$x\in L \Leftrightarrow\exists y\in\Sigma^{*}$ 使得 $(x, y) \in R$ 且 $|y|\in O(|x|^k)$；並且
- 語言 定義在 $\Sigma\cup\{\#\}$ 上的 $L_{R} = \{ x\# y:(x,y)\in R\}$ 能夠被一台確定性圖靈機在多項式時間內判定。

能夠判定 $L_R$ 的圖靈機，便被稱為 $L$ 的驗證器，而那個能使得 $(x, y) \in R$ 邏輯成立的 $y$，被稱為 $x$ 屬於 $L$ 的成員證書。

並非所有的驗證器都必須被限制在多項式時間內。但核心在於：要使得某個語言 $L$ 歸屬 NP 類別，就必須存在至少一個能夠在多項式時間內運行完畢的驗證器。

#### 示例

設

$$\mathrm{COMPOSITE} = \left \{x\in\mathbb{N} \mid x=pq \text{ 对于整数 } p, q > 1 \right \}$$

$$R = \left \{(x,y)\in\mathbb{N} \times\mathbb{N} \mid 1<y \leq \sqrt x \text{ 且 } y \text{ 整除 } x \right \}.$$

判斷一個特定值 $x$ 是否為合數的問題，本質上等價於判斷 $x$ 是否有資格成為集合 COMPOSITE 的成員。通過驗證它是否契合上述定義，學術界可以證明 COMPOSITE ∈ NP。

後來，隨著AKS質數測試算法的提出，進一步證明了 COMPOSITE 其實也歸屬於P類。

### NP完全性

關於NP完全性，學術界有著等價的表述方式。

設 $L$ 是一個定義在有限字母表 Σ 上的語言集合。

$L$ 被稱為「NP完全」，若且唯若它滿足以下兩個條件：

- $L \in \mathsf{NP}$；並且
- 任何其他屬於 NP 類別的語言 $L'$，都能夠在多項式時間內歸約至 $L$（記作 $L' \leq_{p} L$）。這裡的 $L' \leq_{p} L$ 成立，若且唯若滿足以下兩條規則：
- 存在一個轉換函數 $f$ : Σ* → Σ* 能夠使得對於 Σ* 中的所有輸入 $w$，都有一個絕對成立的等式：$(w\in L' \Leftrightarrow f(w)\in L)$；並且
- 存在一台擁有多項式時間極限運算能力的圖靈機，在接收到任何輸入 $w$ 時都保證能停機，且輸出必須是 $f(w)$。

換言之：如果 $L \in \mathsf{NP}$，並且剛好有另外某個已知的NP完全問題，能夠在多項式時間內歸約至 $L$，那麼 $L$ 本身便也成為NP完全問題。這也是電腦科學家在證明某個新問題為NP完全時最常用的方法。

## 宣稱的解答

儘管P與NP問題被公認為尚未被攻克的懸案，但這擋不住無數業餘愛好者，乃至一些專業研究人員公開宣稱自己已經找到了答案。學者格哈德·沃金格曾匯總了一份清單，記錄了1986年到2016年三十年間出現的116份未經驗證的證明文件；這其中，有61份致力於證明 $\mathsf{P} = \mathsf{NP}$，49份認為 $\mathsf{P} \neq \mathsf{NP}$，還有6份宣稱證明了其他結果（比如斷言該問題是不可判定的）。有些解答甚至曾誤導媒體引起短暫的轟動，但這些嘗試在經歷學術審查後最終全都被否定。

## 流行文化

電影《推銷員 (2012年電影)》（Travelling Salesman）描繪了四位被美國政府秘密聘請試圖破解P/NP難題的數學家，在面臨道德與國家機器時的掙扎故事。

在神劇《辛普森一家》第七季第六集「樹屋驚魂VI」中，荷馬（Homer）意外跌入「三維空間」後，畫面背景的特定數字裡便出現了 $\mathsf{P} = \mathsf{NP}$ 的彩蛋。

在美劇《基本演繹法》第二季的第二集《求解X》（Solve for X）中，現代版的福爾摩斯和華生調查了幾起謀殺案，線索表明受害者都是正致力於解決P/NP問題的數學家。

## 類似問題

- R 與 RE 問題的對決，這裡的R類地位類似於P類，而RE類則對標了NP類。這兩個類別在本質上並不相等，因為在這個體系中，確實存在著擁有無法判定性、但其結果卻能夠被快速驗證的問題，例如歸屬於RE完全問題的希爾伯特第十問題。
- 在代數複雜性理論中，也存在著一個類似的問題：VP 與 VNP 之爭。它的答案目前與 P/NP 問題一樣懸而未決。
- FPT 與 W階層問題，則是參數化複雜性領域中，對標P/NP架構的同款級難題。

## 外部連結

- Aviad Rubinstein's Hardness of Approximation Between P and NP , winner of the 美國電腦協會 (ACM) 2017 Doctoral Dissertation Award .