2-SAT

释义 Definition

2-SAT（二元可满足性问题）：布尔可满足性（SAT）问题的一个特殊形式，其中每个子句（clause）最多包含两个文字（literal）。2-SAT 可在多项式时间内求解（常用方法是构建蕴含图并做强连通分量判断）。（SAT 还有更一般的形式，如 3-SAT 等。）

发音 Pronunciation (IPA)

/ˌtuː ˈsæt/

例句 Examples

2-SAT can be solved in polynomial time.
2-SAT 可以在多项式时间内求解。

We reduced the scheduling constraints to a 2-SAT instance and checked satisfiability using an implication graph.
我们把排程约束化简为一个 2-SAT 实例，并用蕴含图来检查是否可满足。

词源 Etymology

2-SAT 来自 “2” + “SAT”。其中 SAT 是 satisfiability（可满足性）的缩写，指布尔公式是否存在一组真假赋值使其为真；“2-” 表示每个子句最多含两个文字，因此称为 2-SAT。

相关词 Related Words

• Sat
• Satisfiability
• Boolean
• Clause
• Literal
• Implication
• Graph
• Strongly Connected Components
• 3-Sat
• Np-Complete

文学与著作 Literary Works

• Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）：讨论 SAT/NP 完全性背景，常与 2-SAT、3-SAT 对照出现。
• Introduction to Algorithms（CLRS）：在图算法/可满足性相关内容中常提到用图方法处理 2-SAT。
• Algorithm Design（Kleinberg & Tardos）：以建模与归约的视角讲解 2-SAT 的典型解法与应用场景。