布林可滿足性問題（boolean satisfiability）

布林可滿足性問題 SAT，是一道關於邏輯開關的是非謎題。給你一條由真／假變數透過 AND（且）、OR（或）、NOT（非）連起來的公式，你只須回答一個問題：有「沒有任何一種」把這些開關各設為真或假的方式，能讓整條公式為真？這就是把「這些限制能否同時被滿足？」剝到只剩純邏輯的問題。

SAT 最常以合取範式（CNF）陳述：公式是若干子句的 AND，而每個子句是若干文字的 OR，其中文字是一個變數或其否定。像 (x1 OR NOT x2 OR x3) 這樣的子句要求其中至少一個文字為真；AND 則要求每個子句同時被滿足。SAT 問是否有某個對 x1、x2、x3、…的真／假賦值同時滿足所有子句。例如 (x1 OR x2) AND (NOT x1 OR NOT x2) 是可滿足的：設 x1 為真、x2 為假。相對地 x1 AND (NOT x1) 不可滿足，沒有任何設定管用。

SAT 是第一個被證明為 NP 完全的問題，由 Cook-Levin 定理證得，這使它成為這套理論在歷史與概念上的中心。驗證一個「是」很容易（代入賦值並求值，是個乾淨的多項式時間驗證器），所以 SAT 屬於 NP；Cook-Levin 證明它也是 NP 困難。實務上 SAT 無所不在：硬體與軟體驗證、規劃、排程、密碼分析全都歸約到它。儘管它是 NP 完全，工業級 SAT 求解器仍能例行地攻克數百萬個變數的公式，這醒目地提醒我們：最壞情況的難度不代表每個實例都難。