3-SAT

释义 Definition

3-SAT（three-sat）指一种经典的布尔可满足性问题：给定一个由若干个“子句”（clause）组成的逻辑公式，每个子句都是恰好 3 个文字（literal，变量或其否定）的“或”（OR）连接，问是否存在一组布尔赋值（True/False）使整个公式为真。它是计算复杂性理论中著名的 NP 完全（NP-complete）问题之一。（更一般的形式是 SAT / k-SAT。）

发音 Pronunciation

/θri st/

词源 Etymology

“3-SAT”来自“3”+“SAT（satisfiability，可满足性）”。SAT 最早系统化地出现在逻辑与计算理论中；3-SAT 则因其在复杂性理论中常用作归约起点而广为人知，尤其用于证明其他问题是 NP 完全的。

例句 Examples

3-SAT is NP-complete.
3-SAT 是 NP 完全问题。

We reduced the scheduling problem to 3-SAT to show it is computationally hard in the worst case.
我们把排班问题归约到 3-SAT，从而证明它在最坏情况下计算上很困难。

文学与著作 Literary Works

Michael R. Garey & David S. Johnson，《Computers and Intractability: A Guide to the Theory of NP-Completeness》以 3-SAT 作为经典 NP 完全问题与归约示例之一。
Michael Sipser，《Introduction to the Theory of Computation》在 NP 完全性章节中常用 3-SAT 进行多项式时间归约讲解。
Christos H. Papadimitriou，《Computational Complexity》讨论 SAT/3-SAT 与 NP 完全性的核心地位及相关证明思路。