近似困難性（hardness of approximation）
近似演算法提出一個交易：我無法快速給你確切的最佳答案，但能給你一個可證接近的答案。一個自然的顧慮是：你是否總能談成這筆交易？對某些問題，令人失望的答案是「不能」：連找出一個大致好的答案本身都是 NP 困難的。近似困難性研究的正是這些極限——證明除非 P = NP，否則沒有多項式時間演算法能把某問題近似得比某個特定比率更好。
怎麼能證明「近似」很難？突破性的工具是 PCP 定理（有自己的條目）。粗略地說，它讓我們把一個 NP 問題重新編碼，使其產生一道「缺口」：「是」實例幾乎可被完全滿足，而「否」實例無法被滿足到超過某個比例，中間沒有過渡。任何把最佳值近似得夠接近的演算法，都將不得不區分這兩種情況——而這個區分恰好精確地解開了原本的 NP 完全問題。所以一個好的近似演算法將蘊含 P = NP。這個「製造缺口」的歸約，是每個不可近似結果的核心。
由此浮現的圖像豐富而參差，值得認真看待。有些問題（如度量型 TSP 或頂點覆蓋）近似得很好；有些只能近似到一個尖銳的門檻、再多就不行（除非 P = NP，MAX-3SAT 無法被近似到超過 7/8，這是一個緊的結果）；還有少數，如一般圖著色或最大團，根本無法在任何合理倍數內被近似。誠實的教訓是：「近似一下就好」並非逃離 NP 困難的萬用後門：對某些問題而言，近似被證明和精確求解一樣難。
對 MAX-3SAT（盡量滿足最多子句），一個微不足道的隨機賦值平均就已滿足 7/8 的子句。醒目的 PCP 型定理說你無法勝過它：任何能保證高於 7/8 比例的多項式時間演算法都將蘊含 P = NP。所以 7/8 不只是容易——它基本上就是可達成的極限，一道完美緊貼的牆。
一個「缺口」歸約（建立在 PCP 定理上）使「近似得夠接近」和精確解 NP 一樣難。
不可近似結果是有條件的：它們說「除非 P = NP，否則不存在好的近似」。它們本身並不證明 P 不等於 NP；而是證明「勝過某門檻」與未解的 P 對 NP 問題一樣難。