JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

NP 完全動物園與 P 對 NP 問題

Cook-Levin 給了你一個錨——SAT 是 NP 完全的。這篇終章把它向外串成一整座難題動物園，帶你真正動手建一個歸約（3-SAT 到團，一步一步來），最後正面迎向那個百萬美元的問題：P 等不等於 NP，而在答案揭曉之前我們又該怎麼辦？

先一個錨，再拉一條鏈

上一篇的結尾，你手裡握著一個得來不易的事實：Cook-Levin 定理證明了 SAT 是 NP 完全的。再回想一下這個分量十足的詞究竟是什麼意思，因為這裡的一切都吊在它身上。一個問題是 NP 完全的，當它同時在 NP 裡（一份簡短的證書能被驗證器在多項式時間內檢查），又是 NP 難的（NP 裡每一個問題都能在多項式時間歸約到它）。所以 SAT 是一個萬用的標靶：你叫得出名字的任何 NP 問題，都暗地裡翻譯成一個 SAT 問句。這就是一個被敲進基岩的錨。

美妙的地方在這裡，而這也正是這篇存在的理由。從頭證明 Cook-Levin 是殘酷的——你得用布林變數去模擬一台任意的非確定型圖靈機。但你再也不必那樣做了。一旦一個問題已知是 NP 完全的，你就能用一招便宜得多的辦法，把第二個問題也升格為 NP 完全：證明第二個在 NP 裡，再給出一個從某個已知 NP 完全問題出發、抵達它的多項式時間歸約。歸約可以串接，所以新問題透過這條鏈，繼承了整個 NP 的困難度。動物園就是這樣壯大的：不是上千場折磨人的圖靈機模擬，而是上千次便宜的翻譯，每一次都站在前一次的肩膀上。

逛一圈動物園

如今已知的 NP 完全問題有數以千計，橫跨邏輯、圖、數字與排程——但一小撮核心問題承擔了大部分作為歸約來源的工作。來見見這些常客。3-SAT 是把 SAT 修剪到每個子句恰好三個文字；它仍然是 NP 完全的，也是最受歡迎的起點，因為它僵硬的形狀容易翻譯。團（CLIQUE）問一張圖裡有沒有 k 個兩兩相連的頂點。頂點覆蓋問有沒有 k 個頂點碰得到每一條邊。漢彌頓路徑問有沒有一條把每個頂點恰好走訪一次的路線，而它加權的表親旅行推銷員問題則問在某預算下最便宜的這種巡迴。子集和問給定數字裡有沒有某個子集剛好湊到目標，而圖著色問一張地圖能不能用 k 種顏色著色，使相鄰者不撞色。

這座動物園有兩件事會讓新手吃驚。第一，所有這些問題在一個精確的意義下同樣難：因為每個都能在多項式時間歸約到其他的，任何單一個問題的快速演算法，立刻就會給出每一個問題的快速演算法——以及整個 NP 的。它們不是一張難度排行榜；它們是同一種難度穿著許多套戲服。第二，難的版本永遠是判定形式（「有沒有大小為 k 的團？」這種是非題），因為複雜度類別是定義在語言之上的——也就是是非實例所成的集合。最佳化版本（「最大的團有多大？」）至少一樣難，而有了判定神諭，你就能用對 k 的二分搜尋把最佳值釘出來。

心裡備一張地圖，標出歸約箭頭通常往哪流：從 3-SAT 你能抵達團與各種圖問題；從團，一行小技巧就到頂點覆蓋（一張圖裡大小為 k 的團，恰好就是它補圖裡大小為 n-k 的頂點覆蓋）；從 3-SAT 你也能造出漢彌頓路徑的小裝置，再從那裡到 TSP；而 3-SAT 透過把子句編碼成精心挑選的數位，便能抵達子集和。當你面對一個新問題、又懷疑它很難時，你的第一直覺該是：「這個最像哪隻動物園常客，我能不能從牠那裡翻譯過來？」

動手建一個歸約：3-SAT 到團

光是抽象地談「翻譯器」，要等到你親手建過一個才會豁然開朗，所以我們來把 3-SAT 歸約到團——人人都會學的那個經典首作歸約。目標是：給定任何一個 3-SAT 公式，在多項式時間內產出一張圖與一個數 k，使這張圖恰恰在公式可滿足時擁有一個大小為 k 的團。拿那個有 k 個子句的小公式，比如 (x 或 y 或 非z) 且 (非x 或 y 或 z) 且 …… 。我們會把每個子句變成一叢三個頂點——每個文字一個——並用一條巧妙的規則，把不同叢之間的頂點連起來。

  1. 為 k 個子句中的每一個，往圖裡放下三個頂點，每個用該子句裡的一個文字標記。一個有 k 個子句的公式給出 3k 個頂點，分成 k 個三元組。三元組內部不放任何邊——同一子句的三個文字彼此永不相連。
  2. 現在，當兩個位於不同三元組的頂點，其文字彼此相容——也就是它們不是對方的否定（x 可以連 y、非y 或 z，但 x 絕不可連 非x）——就在它們之間加一條邊。這條單一規則，就是整個歸約的引擎。
  3. 把目標團大小設為 k，也就是子句的個數。輸出這張圖與這個 k。數一數頂點與邊，整個構造顯然對公式大小是多項式的——幾秒鐘的記帳工夫，不含任何搜尋。
  4. 驗證那雙向的承諾。若公式可滿足，就從每個子句各挑一個為真的文字；這 k 個頂點分處不同的三元組、且兩兩相容（一個滿足賦值絕不會讓 x 與 非x 同時為真），所以它們構成一個 k-團。反過來，一個 k-團必定每個三元組各用一個頂點（三元組內無邊），且絕不自相矛盾（x 與 非x 之間無邊），所以把那些文字讀作為真，就得到一個相容的滿足賦值。
Formula:  C1 = (x OR y OR NOT z)    C2 = (NOT x OR y OR z)

Triple for C1:   [x]   [y]   [NOT z]      (no edges inside)
Triple for C2:   [NOT x]  [y]  [z]         (no edges inside)

Edges across triples = consistent literals only:
   C1.x  --  C2.y        (x, y differ      -> OK)
   C1.y  --  C2.z        (y, z differ      -> OK)
   C1.x  --  C2.x ?      (x vs NOT x       -> NO edge)

Ask: is there a clique of size k = 2 ?
   pick C1.y and C2.y  -> consistent -> clique of 2  -> SAT
   (set y = TRUE satisfies both clauses)
在一個兩子句公式上的 3-SAT 到團小裝置。每個文字一個頂點，子句內無邊，只在不同子句間相容的文字之間連邊。大小為 k（子句個數）的團存在，恰恰當公式可滿足時。

退一步，欣賞一下剛才發生的事。兩個看來毫無相似之處的問題——一個邏輯謎題與一個圖謎題——竟是同一個問題的化身，由一個你能用兩句話講清楚的小裝置連了起來。這個等價透過鏈雙向流通：團如今是 NP 完全的了（它在 NP 裡，而本身就是 NP 完全的 3-SAT 歸約到它）。你建的每一個歸約，都為這張網多牽一條線，而團是難的這個證明，一次都沒提到圖靈機——它整個倚靠著 Cook-Levin 早已敲下的那個錨。

百萬美元的問題

現在來談那個著名的問題，誠實地陳述它。P 裡的每個問題——可在多項式時間求解的——也都在 NP 裡，因為如果你能快速求解某件事，你當然能快速檢查一個被提出的答案（忽略證書，直接把它解出來就好）。所以 P 是 NP 的子集；這一部分已成定論。沒解決的問題是這個包含關係是否嚴格：NP 裡是不是有一個問題，真的不在 P 裡？P 對 NP 問題問的正是這個。若 P = NP，那麼對每個答案容易檢查的問題，答案也都容易找出——那個拼好之後一眼就能驗證的拼圖，拼起來也會很容易。若 P 不等於 NP，那麼檢查就根本地比求解容易，而那些 NP 完全問題就永遠在快速可及的範圍之外了。

為什麼有人這麼在乎？因為你剛學會建的那條鏈。如果連一個 NP 完全問題——SAT、團、動物園裡隨便哪隻——有了多項式時間演算法，那麼透過歸約，整個 NP 都會塌進 P 裡，P 就會等於 NP。反過來，證明任何單一個 NP 完全問題沒有多項式演算法，就會證明 P 不等於 NP。所以整個問題都壓在我們所知最難的那些問題上，而它們全都一起沉浮。誠實的當前進展是：這個問題自 1971 年起就懸而未決，幾乎人人都相信 P 不等於 NP，但沒有人就任一方向證明過它，而它還掛著一百萬美元的克雷千禧獎。當有人隨口說它「顯然」成立或「基本上解決了」，要當心那種虛假的篤定——兩者皆非。

所以你的問題是 NP 完全的。然後呢？

假設你已經證明了你那個現實世界的問題是 NP 完全的。這不是死刑判決——而是一次改道。NP 完全的結論告訴你：別再獵尋一個對每個輸入都管用的快速精確演算法，改去選擇你願意放棄什麼。與 NP 完全性共處本身就是一門手藝，而出口有四扇可靠的門，每一扇都交出不同的東西。

  1. 放棄精確：用一個近似演算法，它跑得快，又能可證明地落在距最佳解（比如說）兩倍以內。對頂點覆蓋，一個貪婪挑邊的技巧保證至多是最佳值的兩倍。但要注意——有些問題抗拒這招：對某些目標，連找出一個好的近似本身都是 NP 難的，這正是近似困難度的主題。
  2. 放棄保證：用一個啟發式——局部搜尋、模擬退火、基因演算法——它通常能快速找到很棒的答案，卻什麼也不承諾。現代 SAT 求解器是這方面的勝利：儘管 SAT 是那個開山祖師級的 NP 完全問題，工業級求解器在實務中冒出來的那些實例上，常規地破解含上百萬個變數的公式。
  3. 放棄一般性：也許你真實的輸入總帶著某種特殊結構。參數化（固定參數）易解性孤立出一個小參數 k——比如解的大小，或圖的樹寬——並給出讓爆炸只被困在 k 裡的演算法，執行時間形如 f(k) 乘以 n 的多項式。若 k 在你的應用裡保持很小，那麼這問題即便在一般情況下是 NP 完全的，也變得溫馴了。
  4. 放棄規模：若你的實例真的很小，一個精確的指數演算法——巧妙的分支定界，或對子集做動態規劃——也許就乾脆能在時限內跑完。知道你的問題是 NP 完全的，恰恰告訴你那道天花板在哪，於是你能為它編好預算，而不是被打個措手不及。

這就是整段旅程，被帶回了家。你以一個預感開啟這一階——有些問題容易檢查卻看似難以求解——並用驗證器與證書讓它變得精確。你學到非確定性給了同一個類別第二張臉，學到歸約能轉移困難度，也學到 Cook-Levin 把整座建築錨定在 SAT 上。這篇把那個錨串成一座動物園，教你用一個小裝置鍛出一條新的鏈環，毫不退縮地面對了懸而未決的 P 對 NP 問題，並說明「NP 完全」是一個開端，而非終點。你從第一台像旋轉閘門的 DFA 起就在描繪的那張計算地圖，如今標上了它最難、也最誠實的邊疆——而那誠實的標記寫著：我們還不知道那條界線究竟落在何處。