3-SAT（三元可滿足性）
/ three-sat /
3-SAT 是加上一條整潔規則的 SAT：每個子句必須「恰好」含三個文字。所以一個實例是許多子句的 AND，每個子句是恰好三個「變數或其否定」的 OR，像 (x1 OR not x2 OR x3) AND (not x1 OR x3 OR x4) AND ...。問題和 SAT 一樣——我們能否設定變數使每個子句同時為真？——但這種一致的形狀使 3-SAT 成為困難性證明最受青睞的起點，因為從一個整齊、固定寬度的公式做歸約，遠比從任意纏結的邏輯做歸約容易設計。
值得注意的是，把每個子句限制為三個文字「並不」讓問題變容易：3-SAT 仍是 NP 完全。（相對地，每個子句兩個文字的 2-SAT『可』在多項式時間內解出——所以「三」正是難度開始發作之處。）3-SAT 為 NP 完全的證明，是把一般的 SAT 歸約到它，靠新的輔助變數把肥大的子句砍成寬度 3。一個超過三個文字的子句，比方 (a OR b OR c OR d OR e)，被改寫成 (a OR b OR y1) AND (not y1 OR c OR y2) AND (not y2 OR d OR e)，引入新變數 y1, y2 把原本的文字串接起來。你可以驗證這種改寫保持可滿足性：原子句可滿足，恰好就在新的合取式可滿足時，因為輔助變數總能被設定成沿著鏈「踢皮球」，直到某個原文字為真。短子句則靠重複一個文字補足到寬度 3。整個轉換是多項式的，所以 SAT <=p 3-SAT，而既然 SAT 是 NP 完全，3-SAT 也是。
實務上為何偏愛 3-SAT 勝過 SAT？因為它僵硬的、每子句三文字的結構，給歸約一副可預測的鷹架。教科書裡幾乎每個經典的 NP 完全性證明都從 3-SAT 出發：每個子句變成一個小裝置（一小段圖片段或算術小機關），三個文字對應三個選擇，而這些裝置被接線成「滿足公式」對應「解出目標問題」。歸約到團、頂點覆蓋、獨立集、圖著色、漢米頓迴路與子集合加總全都倚賴這一點。一個誠實的提醒以避免誘人的錯誤推論：2-SAT 的多項式時間可解性「不會」延伸到 3-SAT——從兩個文字到三個文字的跳躍，正是「容易」與「（推定）困難」之間真正的界線，鮮明地提醒我們：問題定義的微小改變，可能徹底翻轉它的複雜度。
加寬到 3 的演示：長子句 (a OR b OR c OR d) 變成 (a OR b OR y) AND (not y OR c OR d)，用一個輔助變數 y。若 a 或 b 為真，設 y = 假，使第一個子句成立，第二個則僅在需要時靠 c 或 d 滿足；若改為 c 或 d 為真，設 y = 真，使第二個子句成立，第一個則由 y 罩住。可滿足性被保持，而每個子句現在寬度都是 3。
任何 SAT 公式都可用串接的輔助變數變成等可滿足的 3-SAT 公式——SAT <=p 3-SAT。
三是門檻：2-SAT 屬於 P（可用蘊含圖求解），但 3-SAT 是 NP 完全。別以為限制子句寬度就會變容易——正是寬度 3 之處可解性告終，一個尖銳的教訓：定義上極小的改變就能翻轉複雜度。