不可近似性（inapproximability）

我們看過能近似得很好的問題——頂點覆蓋進到 2、背包進到 (1 + epsilon)。自然的下一問是悲觀的那一個：有沒有問題是我們可證「無法」近似得好，無論多聰明？不可近似性研究的正是這些極限。它證明形如「除非 P = NP，沒有多項式演算法能把這個問題近似得比某某因子更好」的陳述——一個不是關於精確求解、而是關於「能否近似」的下界。

邏輯映照 NP 困難，但瞄準近似。要證一個問題 NP 困難，你把一個已知 NP 困難問題歸約到它。要證一個問題「難以近似」，你建造一個特殊的「製造間隙」歸約：它把一個 NP 困難問題的每個 YES 實例映到一個最佳值「大」的實例，把每個 NO 實例映到一個最佳值「小」的實例，並在「大」與「小」之間保證有一段間隙。現在假設某個多項式演算法能近似到比那段間隙更小的因子。跑它：它的答案會乾淨地落在間隙的某一側，讓你能在多項式時間內分辨原 NP 困難問題的 YES 與 NO 實例——而這除非 P = NP 否則不可能。你能製造的間隙寬度，就成了你能證明的不可近似因子。具體結果：集合覆蓋無法近似得比 (1 - o(1)) ln n 更好；MAX-3SAT 無法近似得比 7/8 + epsilon 更好；而一般（非度量）TSP 根本沒有任何常數因子近似——每個都是「除非 P = NP」。

為何重要：不可近似性告訴你何時該「停止」尋找更好的演算法。若一個問題被證明在因子 c 以上難以近似，那麼追求因子 c - 0.001 就是在追求一個 P = NP 的證明——一個該把心力轉向的訊號，也許轉向特例、啟發式或不同的模型。誠實的提醒：這些是條件性結果，建立在 P != NP（有時是更強的唯一賽局猜想）之上；它們是最壞情況的陳述，所以一個「難」問題在你在乎的實例上仍可能容易；而這些間隙歸約中最深的那些，是由一個關於證明驗證的里程碑定理——PCP 定理——所驅動的，正是它才讓銳利的不可近似性成為可能。