這是我們這個時代需要解決的最重要的未解決的問題之一：P = NP 嗎？討論無疑是復雜而漫長的，但正在取得進展，感覺研究人員終于接近裁決了。

作者：Benjamin Skuse 2024-6-26

譯者：zzllrr小樂（數學科普公眾號）2024-5-24

如果我請你出庭作證，對一長串數字按照從低到高的順序進行排序，與解決一個巨大的數獨難題一樣復雜，你可能會認為我已經失去了理智。你肯定會質疑為什么納稅人的錢被浪費在一個無聊主題的審判上。

然而，將案件告上法庭可能比第一印象所認為的更有價值。判定此類任務的相對難度這種基礎性難題是數學和計算機科學中最致命的問題之一：P與NP問題，自1971年提出以來一直懸而未決。這個問題的解決對現實世界產生巨大影響，影響醫學、人工智能、互聯網安全和許多其他領域。由于這些原因，P與NP問題是克萊數學研究所選出的我們這個時代最重要的七大千禧年獎問題之一。

民事案件

P與NP中的“P”代表“多項式時間”（Polynomial time）。當你增加輸入的大小時，如果（理想版本的）計算機需要相應成比例更長一些的時間來完成其給定的任務，那么這個計算機程序就是以多項式時間運行。列表排序是P問題的一個完美示例，其中有已知且簡單的方法對列表進行排序并驗證列表是否正確排序，并且不會隨著列表長度的增加而以某種荒謬的增長速度消耗時間。

圖釋：對于可以在多項式時間內解決的問題（例如O(n)、O(n2)），隨著輸入的增大，難度如何以合理的速度增長，以及解決其他問題的難度如何以加速的速度增長（例如 O(2?), O(n!)）

展開P與NP的“NP”信息量較少（鄭重聲明，它代表“非確定性多項式時間”，Nondeterministic Polynomial time），但從本質上而言，NP問題雖然很難解決，但很容易驗證。數獨的通用版本 - 不是使用9×9網格，而是允許任意大（n2×n2）的網格 - 是一個NP問題。沒有已知的方法可以比蠻力檢查每個可能填充棋盤的數字組合來更快地解決這個問題。因此，當你增加n時，解決謎題的時間會以指數方式增長；也就是說，它變得非常難以解決，而且難度非常快地增長。然而，驗證解所用的時間仍然是多項式級別的，因為你可以運行相對簡單且快速的算法來檢查所有行、列和宮中輸入的數字是否遵循所有規則；即它仍然很容易驗證。

將你現在所了解的P與NP問題與列表排序聯系起來，并解決一個巨大的數獨難題，哪個更難解決的問題的答案似乎更加明顯 – 毫無疑問是列表排序！如果你隨后將同樣的思路應用于大量P問題和NP問題，并在民事法庭上陳述你的發現，那么很容易證明——基于概率的平衡——所有列表排序——類型問題并不等同于所有大型數獨類問題，即P≠NP，你會輕松贏得官司。

刑事案件

圖源：Nick Youngson CC BY-SA 3.0 Alpha Stock Images

但數學家和計算機科學家需要比這更高的證明標準。事實上，社會對證明標準的要求比這更高。因為如果P確實等于NP，原則上，目前棘手的問題就會變得容易。這一事實可以用來做好事——例如優化運輸路線和尋找新藥物——也可以用來做壞事，包括黑客入侵銀行賬戶和政府網站。就像刑事法庭的陪審團確定被告有罪一樣，我們都需要“排除合理懷疑”（beyond reasonable doubt）來知道P=NP是否成立。這是一個更加艱難的提議。

為了實現這一目標，研究人員已經證明，幾乎所有看似困難的NP問題都是“NP完全”（NP-complete）的，這意味著如果他們對一個NP完全問題有一個有效的解，那么它也可以適用于快速解決所有其他NP問題。例如，廣義數獨是NP完全的，因為它可以簡化為其他已知為NP完全的經典復雜問題，包括（明顯相似的）拉丁方完備（LSC，Latin square completion）問題和（表面上看非常不同的）哈密頓環路（Hamiltonian cycle）問題。從精確的數學意義上來說，它們是等價的。

因此，為了證明P是否等于NP，勇敢的研究人員所要做的就是發現一種巧妙的算法技巧，可以在多項式時間內解決NP完全問題（P = NP），或者只需找到一個他們可以證明任何計算機程序都無法快速解決的NP完全問題（P ≠ NP）。然而，盡管一些最聰明的人經過半個世紀的努力，這兩條路仍然難以捉摸。

復雜問題的復雜度

近年來，許多研究人員不再嘗試直接求解P與NP問題。相反，他們一直在質疑解決P與NP以及類似問題一開始就很困難的原因。他們一直在問諸如“確定各種計算問題的難度有多難？”之類的問題。以及“為什么很難確定它們有多困難？”這些及其他“元”問題是數學和計算機科學領域稱為“元復雜度”（meta-complexity）的基礎。既是一個研究主題，也是研究人員試圖用來解決P與NP等問題的工具。

目前元復雜度研究人員的一個重要關注點是一個歷史悠久且仍然無法明確分類的特殊問題：最小電路門數問題（MCSP，Minimum Circuit Size Problem）。MCSP之所以有趣有幾個原因，尤其是因為它是少數具有挑戰性的計算復雜度問題之一，目前尚不清楚它是否是NP完全的。

MCSP被發現在密碼學、證明復雜度、學習理論和電路下界等不同領域發揮著核心作用，它提出的問題是：你能確定用于計算布爾函數的黑盒假設計算機具有高的還是低的電路復雜度嗎？布爾函數將一定數量的0或1作為輸入，并輸出0或1（真或假）。由此，你可以構建一個真值表：輸入值及其相應輸出的所有組合的表格化的表示。本質上，真值表提供了函數的輸入輸出行為，但沒有提供有關函數計算復雜度的信息。這種復雜度用電路復雜度來表示，電路復雜度定義為構建可以計算給定函數的最小電路所需的邏輯門總數。

有了這些澄清，問題就可以更精確地提出：MCSP將布爾函數f的描述看作輸入一個真值表以及電路門數參數s，并詢問“是否存在一個計算f的門數≤s的的電路？”由于MCSP既具有計算方面的復雜度，又與復雜度的計算有關，因此它作為元復雜度的元問題，即元2-復雜度問題并不常見。事實上，研究人員正在試圖找出為什么很難確定MCSP的解決難度，這意味著它可能更具元性；也許是一個元3-復雜度問題。

對于最簡單的布爾函數，MCSP可以通過在多項式時間內運行的算法來求解。但隨著函數變大，絕大多數函數似乎需要指數級增加的邏輯門數量。與廣義數獨一樣，MCSP似乎不可能解決，除非使用蠻力搜索，但如果給出一個解，也很容易驗證。你可以猜測一個電路，運行每個可能的輸入，然后查看輸出是否與給定布爾函數的輸出匹配。因此，這顯然是一個NP問題。但P里也有嗎？它是一個NP完全問題嗎？即，解決它的快速方法是否意味著證明NP中的所有問題實際上都在P中？社區中的許多人懷疑MCSP不在P中，而是NP完全的，如果得到證實，則明確意味著P ≠ NP。

解的進展？

近年來，研究人員在證明MCSP是NP完全的這一方面取得了重大進展。例如，大量證據（其中許多是在過去六年中出現的）表明MCSP的變體是NP完全的。也許最有趣的一些進展是來自東京國家信息研究所的Shuichi Hirahara（平原秀一）取得的。

2018年，Hirahara將MCSP從最壞情況化簡為平均情況。在這里，“平均情況”復雜度是衡量大多數輸入問題的平均容易程度或困難程度的指標，而“最壞情況”復雜度是標準方法，考慮到所有可能輸入的問題的最大復雜度。復雜度對于平均情況和最壞情況可能不同的問題很有趣，因為它們可以提供對這些問題的基本復雜度的見解。Hirahara的結果意味著，假設的平均情況MCSP算法實際上足夠強大，可以解決稍微不同的MCSP版本，該版本限制了允許的電路類型，而不會犯任何錯誤。這個結果令人興奮，因為沒有其他NP完全問題具有已知的最壞情況到平均情況的減少。鑒于所有NP完全問題的等價性，它為研究P與NP問題提供了新的途徑。

接下來，在2022年，Hirahara利用復雜度理論和先進信息論密碼學的結合，證明了部分布爾函數上的MCSP是NP難的（NP難問題與NP完全問題一樣難，但不一定必須在NP中）。部分布爾函數有一個真值表，其中包含常見的0和1，但也包含一些“不知道”符號 - 有些可能是0或1，你并不關心電路是怎樣的。不知何故，添加這種“不知道”的模糊性允許部署許多有用的技術來解決部分MCSP問題，但到目前為止，尚不清楚是否可以應用這些相同的技術來解決原始MCSP問題。

P、NP、NP完全和NP困難等問題集的歐拉圖（Euler diagram）。左側在P ≠ NP的假設下有效，而右側在P = NP的假設下有效。

圖源：Behnam Esfahbod

另一位研究人員，來自麻省理工學院的Rahul Ilango（拉胡爾·伊蘭戈），一直致力于以多種方式證明MCSP的NP完全性，將MCSP的更簡單和更復雜的版本視為解決主要問題的切入點。他最新的元復雜度結果成功地將 MCSP與看似不同的布爾可滿足性問題（SAT）聯系起來，其中將獲得布爾函數作為公式或電路的表示，并詢問有關其函數的信息（例如，它是否具有其真值表中的 1，或者它輸出某種0和1的模式，等等）。

MCSP就是所謂的“黑盒問題”，因為在給定黑盒訪問的情況下，你想了解有關表示的一些信息。布爾可滿足性問題則完全不同。布爾可滿足性問題（SAT）被稱為“白盒問題”，其目標是根據函數的表示來說明有關該函數的一些信息。2023年，Ilango和同事做出了驚人的發現，即SAT通過隨機預言簡化為MCSP，即具有可在P中計算且可供所有電路和計算機訪問的完全隨機函數。由于SAT眾所周知是NP完全的，因此具有隨機預言的MCSP也必須是NP完全的。

這些和其他最近的結果進一步證明了原始MCSP實際上也是NP完全的。而且，如果這是真的，MCSP可以隱藏缺失的證據，“排除合理懷疑”地證明P是否等于NP。

就像問題本身一樣，P與NP的裁決當然是復雜而漫長的，但正在取得進展，而且感覺研究人員終于離結論越來越近了。

圖源：Nick Youngson CC BY-SA 3.0 Alpha Stock Images

關于作者

Benjamin Skuse（本杰明·斯庫斯）是一位專業的科學自由撰稿人。早期他是一名學者，獲得愛丁堡大學應用數學博士學位和科學傳播碩士學位。現在，他居住在英國西部地區，致力于為所有觀眾打造易于理解、引人入勝且有說服力的敘述——無論主題有多復雜。他的作品曾發表在《新科學家 New Scientist》、《天空與望遠鏡 New Scientist》、《BBC仰望夜空，BBC Sky at Night》雜志、《物理世界 Physics World》等雜志上。

參考資料

HLF https://scilogs.spektrum.de/hlf/on-trial-p-versus-np-and-the-complexity-of-complexity/

《量子雜志》復雜度理論的50年探索知識極限的歷程 https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/

哈密頓環路問題 https://www.whitman.edu/mathematics/cgt_online/book/section05.03.html

Hirahara derived https://ieeexplore.ieee.org/document/8555110

Hirahara provedhttps://eccc.weizmann.ac.il/report/2022/119/

千禧年問題 https://www.claymath.org/millennium-problems/

最小電路門數問題（MCSP） https://www.ias.edu/video/expanding-reach-p-not-equal-np-minimum-circuit-size-problem-random-oracle-np-hard

最近的元復雜度結論 https://eccc.weizmann.ac.il/report/2023/165/

布爾可滿足性問題（SAT） https://www.cs.princeton.edu/courses/archive/fall21/cos326/lec/23-01-sat.pdf

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

數學科普不迷路！