當問題很難時：P、NP 與難解性

快速求解與快速驗證

你目前搭建的一切都執行在多項式時間內——代價形如 n、n log n 或 n^2，用[[big-o-notation|大 O 記號]]表示。擁有這樣演算法的問題類被稱為 P（取自 polynomial，多項式）。這些就是我們認為「能高效求解」的問題：隨著輸入增長，工作量以一種可控、可預測的速率增長。

再來一個更微妙的類。NP 是這樣一類問題：*如果有人遞給你一個候選答案，你能快速驗證它*（多項式時間）——哪怕找到那個答案本身可能很難。想像一幅巨大的拼圖：拼好它也許要很久，但驗證一幅已拼好的圖是否正確只需一眼。P 中的每個問題也都在 NP 中（既然你能快速求解，當然也能快速驗證），所以 P 包含在 NP 之內。

        +-------------------------- NP --------------------------+
        |   (answers are checkable fast)                          |
        |                                                         |
        |    +--------- P ---------+        +-- NP-complete --+    |
        |    | solvable fast       |        | hardest in NP   |    |
        |    | (sort, search, MST) |        | (SAT, TSP, ...) |    |
        |    +---------------------+        +-----------------+    |
        +---------------------------------------------------------+

  Open question:  is P = NP ?  i.e. does the P box secretly fill all of NP?

P 位於 NP 之內。兩者是否其實相等——P 那一格是否悄悄填滿了整個 NP——尚不可知。

NP 完全與那個未解之謎

NP 內部住著一個特殊家族：[[np-completeness|NP 完全]]問題。在一種精確的意義上，它們是 NP 中*最難*的問題——而且彼此緊緊相連。我們懂得如何把其中任意一個歸約（reduce）為另一個：在多項式時間內，把問題 A 的一個實例改寫成問題 B 的一個實例，使得解出 B 就解出了 A。正因為這張歸約之網，只要有人為*其中某一個* NP 完全問題找到了快速（多項式時間）演算法，那個演算法立刻就能為*所有* NP 完全問題給出快速解法。

SAT（布林可滿足性）：給定一個邏輯公式，是否存在一組對變數賦真/假的取值，使整個公式為真？驗證一個給定賦值是瞬時的；找出一個才是難處。SAT 是第一個被證明為 NP 完全的問題。
TSP（旅行商問題的判定形式）：給定一組城市和一個預算，是否存在一條在該預算內遍歷所有城市的路線？驗證一條路線的長度很容易；在天文數字般眾多的路線中搜索卻不然。
圖著色、子集和、背包問題的判定形式，還有數以百計的其他問題，全都屬於同一個俱樂部，由歸約相連。快速解出一個，就解出了全部。

面對難題該怎麼辦

假設你已經斷定你的問題是 NP 難的（至少和 NP 完全問題一樣難）。這不是死胡同——而是一次改道。它告訴你別再追求一個完美、快速、精確的演算法，而把力氣花在真能見效的地方。你有幾條誠實的出路。

近似（approximation）：接受一個可證明接近最優、但能被快速找到的答案。對許多 NP 難問題，存在多項式時間的演算法，能保證比如「在最優解的 5% 以內」。
啟發式（heuristics）：使用聰明的經驗法則（貪婪選擇、局部搜索），即便沒有保證，也能在典型輸入上表現良好。它們驅動著現實中的路線規劃器和排程器。
指數級但帶剪枝的精確搜索：當實例不大時，一個邊探索搜索空間、邊砍掉無望分支的精確演算法（分支定界，以及你在回溯中見過的剪枝），實踐中往往能跑完，哪怕最壞情形是指數級。
限制問題：有時你實際面對的特例（一棵樹而非一般的圖、較小的整數權重）存在快速演算法，儘管一般問題沒有。