數獨 愛好者？在深入瞭解遊戲背後的數學原理後，在《大眾科學》遊戲專區用我們自己的謎題測試您的技能！SciAm Games!
計算機科學似乎正處於不可阻擋的進步曲線中。僅僅幾十年，我們就從真空管發展到微晶片，從撥號上網發展到高速網際網路，從Office助手 Clippy 發展到 ChatGPT。然而，科學和工業領域的成千上萬個日常問題對於當今的人工智慧超級計算機來說仍然像以往一樣無法解決。
這些出了名的難題“NP完全問題”懸賞 百萬美元獎金，由非營利組織克雷數學研究所頒發，獎勵那些找到快速解決方案或證明不存在解決方案的人。20世紀70年代的一個驚人見解讓這一挑戰更具吸引力：那一千多個問題在深層意義上是同一個問題。如果您解決了一個，就解決了所有問題。這個概念現在是理論計算機科學領域的基礎，它表明某些計算問題組形成了一個統一的網路。發現一種可以快速解決任何大小的 數獨謎題 的演算法，您現在就可以 破解保護我們數字經濟的加密方案。揭示在預算內安排飛行旅行的捷徑，您就可以用它來解決幾乎任何著名的未解決 數學難題。
找到這些NP完全問題的快速演算法（或證明不存在此類演算法）將解決“P與NP”問題，這是計算機科學中最重要的謎題。P指的是計算機可以有效解決的計算問題集。同時，NP代表其解決方案可以有效驗證的問題。但這些問題不一定能快速解決。NP包括P中的所有問題（因為找到解決方案是驗證它的一個很好的方法），但也包括我們不知道有效方法來找到解決方案的更難的問題。我們只能在它們被解決後才能驗證它們。P與NP問題詢問，在找到解決方案和驗證解決方案之間，這種明顯的不對稱性是真實存在還是虛幻的。也許P = NP，它們指的是同一組問題。換句話說，也許我們不知道如何有效解決的NP問題相對於P問題而言，只是因為我們尚未找到正確的見解而顯得困難。
關於支援科學新聞
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道： 訂閱。透過購買訂閱，您正在幫助確保未來能夠繼續講述關於塑造我們當今世界的發現和想法的具有影響力的故事。
例如，是否存在一種演算法（一系列簡單指令），給定任何大型城市列表、連線它們的航班以及預算，可以有效地決定您是否可以在預算範圍內訪問所有城市？我們不知道。我們確實知道一種低效的演算法：檢查訪問所有城市的每種可能的航班順序，將每種順序的成本加起來，並將總成本與預算進行比較。但是，隨著列表中的城市數量增加，要檢查的路線數量呈指數級爆炸式增長，即使對於 最快的計算機 來說，也很快變得不可行。可能存在也可能不存在某種巧妙的捷徑可以規避這種詳盡的搜尋，但計算機科學家尚未找到它。然而，給定一個解決方案——在本例中是一個擬議的航班列表——人們可以在合理的時間內驗證一條路線是否訪問了每個城市並在預算之內。如果P等於NP，這意味著航班場景（旅行商問題的示例）有一個快速的解決方案。我們只是還不知道。
許多自然的計算問題都與旅行商問題一起歸入NP集。這包括來自物流（例如 將箱子裝入卡車）、社交網路（尋找共同朋友的派系）、生物學（預測蛋白質如何摺疊）以及遊戲（如 數獨、寶可夢 和 糖果粉碎傳奇）的挑戰。我們甚至可以將數學本身視為一個NP問題，因為它的證明可以有效地驗證。當人們每天將箱子裝入卡車並解決數獨問題時，將這些問題歸類為“難題”似乎很奇怪。但是，我們認為只有當演算法能夠有效地解決每個例項（包括非常大的例項）時，該演算法才能有效地解決問題。“高效”的嚴格定義取決於解決問題所需的時間如何隨著輸入規模的擴大而擴充套件。當然，計算機解決9×9數獨的速度比解決一百萬乘一百萬的數獨要快，因此“高效”的嚴格定義取決於解決問題所需的時間如何隨著輸入規模的擴大而擴充套件。
P與NP問題涉及各種計算問題以及它們彼此之間的關係，因此，似乎需要單獨研究每個問題才能解決這個問題。假設您發現了一種解決旅行商問題的有效演算法。這將是一個英雄般的突破，但它是否會告訴您任何關於您解決巨型數獨或任何其他具有挑戰性的NP問題的能力的資訊？令人驚訝的是，您解決該單個問題的演算法將完全解決P與NP問題。1972年，計算機科學家理查德·卡普發表了一篇 開創性的論文，證明了21個經典的NP問題具有一個顯著的特性：解決其中任何一個問題的有效演算法不僅可以用於解決其他20個問題，而且可以用於解決NP中的每個問題。他將這21個問題稱為NP完全問題。在隨後的幾年裡，隨著研究人員發現許多其他NP問題也具有這種神奇的特性（包括旅行商問題），這個列表變得越來越長。
我們可以用樂觀或悲觀的態度來看待NP完全性。從樂觀的角度來看，橫亙在我們與無限技術前景之間的一系列極其困難的問題現在看起來更像是一個紙牌屋。將其中一個問題拉入可行的領域，整個NP體系就會崩潰，一場科學革命將從廢墟中升起，充滿了輕鬆高效的旅行、透過蛋白質摺疊快速 發現藥物 以及數學的新時代。從悲觀的角度來看，NP完全性表明這些問題沒有有效的演算法；如果證明事實並非如此只需要征服一個問題，那麼為什麼還沒有人成功呢？大多數專家 傾向於 後一種解釋，並懷疑NP完全問題沒有快速演算法。
無論以樂觀還是悲觀的角度來看待，完整問題的概念都改變了研究人員看待計算的方式。卡普表明，他可以使用解決一個NP完全問題的演算法來解決另一個問題，首先要證明您可以使用稱為“歸約”的過程將看似無關的問題翻譯成彼此的語言。其工作原理是展示如何獲取一個問題的任何例項（例如，涉及城市列表、城市之間的航班和預算的問題），並將其轉換為另一個問題（例如，大型 數獨謎題），從而使數獨謎題只有在可以在預算內訪問所有城市時才具有有效解（否則沒有有效解）。這樣，如果您發現了一種解決數獨問題的有效演算法，那麼您可以透過將旅行商問題的例項轉換為數獨謎題，使用該演算法來解決旅行商問題。（請檢視本文末尾，瞭解有關歸約的詳細示例。）
這種使用一種問題的語言來編碼另一種問題的能力不僅是這個例子的怪癖，也是計算本身的一個特徵。歸約網路將所有NP完全問題聯絡在一起。解決其中任何一個問題，您就可以解決任何其他NP問題。其含義令人難以置信。請記住，我們可以將證明數學定理構架為一個NP完全問題。選擇任何著名的未解決數學問題。NP完全性理論告訴我們，存在某個級別的 糖果粉碎傳奇，它完美地編碼了您的數學問題。如果在這個級別的糖果粉碎傳奇中，在一定步數內可以達到一定的分數，那麼您的數學問題就有一個特定長度的證明；否則就沒有。NP完全性還向我們保證，蛋白質摺疊（或箱子包裝或數獨求解）方面的某些進展將摧毀數字經濟。這是因為保護我們敏感資料的加密是透過將它們隱藏在被認為難以解決的計算問題背後而工作的。（值得注意的是，雖然解決NP完全問題可以讓您破解加密，但反之則不然；大多數加密方案背後的難解問題本身並不完全是NP完全問題。）
由於所有這些都與NP完全問題息息相關，因此一百萬美元對於它們的解決方案來說可能看起來像是便宜貨。下次當您努力安排假期旅行或破解數獨謎題時，這可能會給您帶來一些額外的動力。
歸約是如何工作的？
對於任何想要更深入瞭解歸約如何工作的人，讓我們將另一種NP完全問題“地圖三著色問題”歸約到“團問題”。地圖三著色問題 問道：給定一張地圖，您能否為每個區域分配三種顏色之一，以使相鄰區域不重複顏色？團問題則問道：給定一個社交網路，它是否包含一組所需數量的、彼此都是朋友的人？這兩個問題都是NP完全問題，這意味著我們不知道任何解決它們的有效演算法。表面上看，它們幾乎沒有共同之處。但我們將展示，給定一張地圖，我們可以將其轉換為社交網路，以便社交網路問題的答案將為我們提供地圖問題的答案。
想象一下美國地圖。為了從中構建一個社交網路，我們將為每個州指定三個“人”，每種顏色（藍色、綠色和紅色）各一個。然後，我們將使兩個人成為朋友，除非：
他們代表同一個州。（威斯康星州的綠色代表不會與威斯康星州的藍色代表成為朋友。）
他們具有相同的顏色並代表相鄰的州。（北達科他州和南達科他州共享邊界，因此它們的紅色代表不會成為朋友，但北達科他州和佛羅里達州不相鄰，因此它們的紅色代表將成為朋友。）
我宣告，只有當美國地圖具有有效的三著色時，這個由150人組成的社交網路才會包含一個由50個共同朋友組成的團。如果我們在網路中找到了50個共同朋友，他們必須都代表不同的州，因為根據設計，當他們代表同一個州時，我們沒有讓他們成為朋友。此外，與團對應的著色永遠不會為相鄰州分配相同的顏色——我們明確禁止了網路中的此類連結。因此，一個由50人組成的團將對應於一個有效的三著色。同樣，如果網路中不存在50-團，則地圖也不存在三著色。
我們剛剛歸約了地圖三著色問題到團問題。這意味著，如果有人發現瞭解決團問題的快速演算法，那麼他們可以使用它來解決地圖三著色問題的任何例項。至關重要的是，第一步——將地圖轉換為網路——是快速的。在網路中建立人和適當的友誼關係不需要任何詳盡的搜尋或其他不可行的計算開銷。歸約表明，即使我們的問題感覺是獨一無二的，它們也可能比它們看起來更具普遍性。
這是一篇觀點和分析文章，作者或作者表達的觀點不一定代表《大眾科學》的觀點。