3-SAT
3-SAT 是帶著一個整齊限制的 SAT：每個子句恰有三個文字。你仍問公式能否被弄成真，但現在每個 OR 群被限制為三個開關，像 (x1 OR NOT x2 OR x3)。這個小小的一致性使 3-SAT 成為幾乎每個 NP 困難證明的主力起點，因為三文字子句的結構恰好足以用來搭建俐落的小元件。
一條 3-CNF 公式是若干子句的 AND，每個子句是恰好三個文字的 OR，每個文字是一個變數或其否定。3-SAT 問：有沒有一個真／假賦值滿足每個子句？了不起的事實是這個受限版仍是 NP 完全。你把一般 SAT 歸約到 3-SAT，靠的是切碎子句：含一或兩個文字的子句用輔助變數補滿，而像 (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 而非單純的 SAT 當歸約來源？因為「恰好三個文字」這個僵硬的形狀，遠比較容易翻譯成圖問題的結構。從 3-SAT 歸約到團、到頂點覆蓋、到圖著色、到漢米頓路徑，正是這領域經典的小元件構造。注意這條邊界：3-SAT 是 NP 完全，但 2-SAT（每子句兩個文字）可在多項式時間內求解。從兩個文字跳到三個，恰恰就是可解性讓位給 NP 完全的地方。
長子句 (a OR b OR c OR d) 變成兩個三文字子句 (a OR b OR y) AND (NOT y OR c OR d)。若原子句靠比如 c 為真而被滿足，就設 y 為假，使第一個新子句需要 a 或 b（未增加限制），第二個則由 c 滿足。這些片段是等可滿足的。
3-SAT 把每個子句限制為三個文字卻仍是 NP 完全，使它成為小元件歸約最愛的來源。
門檻很鋒利：3-SAT 是 NP 完全，2-SAT 屬於 P。別以為「每子句沒幾個文字」就容易；三個就已足以達到完整的 NP 困難。