歸約到頂點覆蓋、團與獨立集（reduction to vertex cover, clique and independent set）

一旦 SAT 與 3-SAT 已知困難，下一步就是把這份困難散播到自然的圖問題上。三個經典問題一起倒下，因為它們其實是同一個問題的三套戲服：團（CLIQUE，找一組兩兩相連的頂點）、獨立集（INDEPENDENT SET，找一組彼此之間沒有邊的頂點），以及頂點覆蓋（VERTEX COVER，找一個碰到每條邊的小頂點集）。本條目就是那條證明三者皆為 NP 完全的歸約鏈，從 3-SAT 出發，把一個邏輯公式變成一張圖。

先講三者之間容易的牽連。在 n 個頂點的圖 G 中，一個集合 S 是「獨立集」，當且僅當 S 是補圖 G'（邊與非邊互換）中的「團」——所以在 G 中找大小為 k 的獨立集，等於在 G' 中找大小為 k 的團，是個多項式時間的轉換。而 S 是獨立集，當且僅當它的補集 V 減 S 是「頂點覆蓋」：每條邊都至少有一個端點落在 S 之外（因為 S 內部沒有邊），所以 V 減 S 覆蓋了所有邊。因此「G 有大小為 k 的獨立集」恰好在「G 有大小為 n 減 k 的頂點覆蓋」時成立。這些給出 clique <=p independent-set <=p vertex-cover 並可反向，所以只要證明「任一個」困難，三者就都困難。現在來看那個種子歸約，3-SAT <=p clique（等價於獨立集）。給定一個有 m 個子句的 3-SAT 公式，建一張圖，每個「文字出現」一個頂點（3m 個頂點，分成 m 個三選一的群）。每當兩個頂點位於「不同子句」「且不互相矛盾」時（你絕不連 x 與 not x），就在它們之間放一條邊。那麼公式可滿足，當且僅當這張圖有大小為 m 的團：一個團必須從每個子句恰好選一個文字（不同子句）且不矛盾，這正好是「每個子句一個為真文字」的一致選擇——一組可滿足指派。這個構造是多項式的，所以 3-SAT <=p clique。

這些歸約是 NP 完全動物園的主力，也是「裝置式」證明的範本：每個子句變成一個小的局部結構，邊把邏輯約束編碼進去，而圖問題的一個解被接線成「一組可滿足指派」的意思。兩個誠實的提醒。方向是固定的：我們把 3-SAT 歸約「進」這些問題以證明「它們」困難，而非反過來。並注意頂點覆蓋是「小集合」問題（最小化），而團與獨立集是「大集合」問題（最大化）——它們透過取補互換位置，這正是為什麼「大小為 k 的獨立集當且僅當大小為 n 減 k 的頂點覆蓋」這樣一個乾淨的事實，能讓一個歸約服務全部三者。同樣的困難性也支配著它們的最佳化版本，這就是為什麼一旦精確求解無望，我們便轉向近似演算法（例如頂點覆蓋的 2 近似）。