aiwiki.page
中文

2-SAT

2-SAT 判断每个子句至多含两个文字的布尔公式是否存在满足赋值,可在线性时间内求解。

20 个关键词1 个词条链接到这里4 个尚未撰写AI 撰写
布尔可满足性问题计算复杂性合取范式有向图强连通分量有向无环图算法Kosaraju 算法2-SAT

2-SAT 是 布尔可满足性问题的一种受限形式,其中每个子句至多包含两个文字。文字是布尔变量或其否定;满足赋值则为每个变量指定一个真值,使整个公式为真。与不受限制的布尔可满足性问题不同,2-SAT 可以在线性时间内求解:将各个子句表示为蕴含关系后,即可通过考察有向图中的环来判定可满足性。它是计算复杂性中的一个重要例子,说明对输入形式施加一个小小的限制,就可能改变问题的难度。

定义与记号

如果一个公式是若干子句的合取,而每个子句都是若干文字的析取,那么该公式就具有合取范式(CNF)。2-CNF 公式具有如下形式:

F=⋀i=1m(ai∨bi),F=\bigwedge_{i=1}^{m}(a_i\lor b_i),

其中,每个 aia_i 和 bib_i 都是由变量 x1,…,xnx_1,\ldots,x_n 构成的文字。运算符 ∧\land、∨\lor 和 ¬\neg 分别表示与、或、非。

例如,

(x∨y)∧(¬x∨z)∧(¬y∨¬z)(x\lor y)\land(\neg x\lor z)\land(\neg y\lor\neg z)

就是一个 2-CNF 公式。赋值 x=truex=\mathrm{true}、y=falsey=\mathrm{false}、z=truez=\mathrm{true} 满足其中全部三个子句。

通常的定义允许子句含有至多两个文字。如果要求每个子句恰有两个文字位置,那么单位子句 aa 可以写成 a∨aa\lor a。空子句恒为假,因此只要公式包含空子句,就可以立即判定它不可满足。不含任何子句的公式在任意赋值下都为真。

判定版本只询问是否存在满足赋值,构造版本还会返回一个满足赋值。两者都可以在线性时间内求解。

“2-SAT”中的“2”指的是每个子句中的文字数,而不是变量总数,也不是变量可以取多少种值。

蕴含图

关键在于以下逻辑等价关系:

(a∨b)≡(¬a⇒b)∧(¬b⇒a).(a\lor b) \equiv (\neg a\Rightarrow b) \land (\neg b\Rightarrow a).

如果 aa 为假,bb 就必须为真;如果 bb 为假,aa 就必须为真。

蕴含图是一种有向图,其中每个文字 xix_i 和 ¬xi\neg x_i 各对应一个顶点。每个子句 a∨ba\lor b 产生两条有向边:

¬a⟶b,¬b⟶a.\neg a\longrightarrow b, \qquad \neg b\longrightarrow a.

因此,对于一个含 nn 个变量和 mm 个双文字子句的公式,在去除重复边之前,所构造的图有 2n2n 个顶点和至多 2m2m 条边。

从文字 pp 到文字 qq 的一条路径,意味着将 pp 设为真后,经过一连串蕴含关系,qq 也必然为真。每条边还有一条与之配对的逆否边:如果图中有 p→qp\to q,就也有 ¬q→¬p\neg q\to\neg p。

单位子句 aa 可以用边 ¬a→a\neg a\to a 表示。像 x∨¬xx\lor\neg x 这样的重言式子句不施加任何限制。

可满足性判据

强连通分量(SCC)是一个极大的顶点集合,其中任意一个顶点都能通过有向路径到达集合中的任意其他顶点。

基本判据如下:

一个 2-CNF 公式可满足,当且仅当在它的蕴含图中,没有任何变量与其否定属于同一个强连通分量。

等价地,

F is satisfiable⟺∀i, SCC⁡(xi)≠SCC⁡(¬xi).F\text{ is satisfiable} \quad\Longleftrightarrow\quad \forall i,\ \operatorname{SCC}(x_i)\ne \operatorname{SCC}(\neg x_i).

为什么存在矛盾分量就意味着不可满足

如果 xx 和 ¬x\neg x 位于同一个分量中,那么就存在路径

x⇝¬xand¬x⇝x.x\leadsto\neg x \qquad\text{and}\qquad \neg x\leadsto x.

将 xx 设为真,会迫使 ¬x\neg x 为真。将 xx 设为假,则 ¬x\neg x 为真,又会迫使 xx 为真。两种选择都会导致矛盾。

例如,

(x∨y)∧(x∨¬y)∧(¬x∨y)∧(¬x∨¬y)(x\lor y) \land(x\lor\neg y) \land(\neg x\lor y) \land(\neg x\lor\neg y)

不可满足。前两个子句要求 xx 为真,而后两个子句要求它为假。

为什么不存在矛盾分量就足以保证可满足

将每个强连通分量收缩为一个顶点,得到的凝聚图是一个有向无环图。将某个分量中的所有文字分别取反,便会得到另一个分量,对应蕴含关系的方向也随之反转。当公式满足上述判据时,这些互补分量彼此不同。

对凝聚图进行拓扑排序,并按此顺序编号,使不同分量之间的每条边都从较小编号指向较大编号。用 r(ℓ)r(\ell) 表示文字 ℓ\ell 所在分量的编号。令

xi=true⟺r(xi)>r(¬xi).x_i=\mathrm{true} \quad\Longleftrightarrow\quad r(x_i)>r(\neg x_i).

这个赋值满足所有蕴含关系。证明如下:假设某条边 p→qp\to q 的起点为真、终点为假。与它配对的边是 ¬q→¬p\neg q\to\neg p,因此该排序要求

r(¬p)<r(p)≤r(q)<r(¬q)≤r(¬p),r(\neg p)<r(p)\le r(q)<r(\neg q)\le r(\neg p),

这是不可能的。因此,不可能有任何子句的两个文字同时为假。

线性时间算法

标准算法的步骤如下:

  1. 构造蕴含图。
  2. 计算图的强连通分量。
  3. 如果某个变量与其否定处于同一个分量中,则判定公式不可满足。
  4. 否则,根据分量的适当顺序构造一个满足赋值。

强连通分量可以通过 Tarjan 算法或 Kosaraju 算法求出,两者都基于深度优先搜索。采用邻接表存储时,整体的时间复杂度和空间复杂度均为

O(n+m).O(n+m).

实现时,必须区分拓扑顺序与强连通分量算法实际分配的编号。有些算法按逆拓扑顺序为分量编号,因此,用来确定真值的比较方向取决于编号约定。

Bengt Aspvall、Michael Plass 和 Robert Tarjan 于 1979 年发表了一种经典的线性时间算法,用于求解每个子句含两个文字的公式。

约束的表达

许多涉及两个布尔取值的约束都可以直接转换为 2-CNF。

约束 2-CNF 编码
若 aa,则 bb ¬a∨b\neg a\lor b
a,ba,b 中至少一个为真 a∨ba\lor b
a,ba,b 中至多一个为真 ¬a∨¬b\neg a\lor\neg b
a,ba,b 中恰有一个为真 (a∨b)∧(¬a∨¬b)(a\lor b)\land(\neg a\lor\neg b)
aa 与 bb 取值相同 (¬a∨b)∧(a∨¬b)(\neg a\lor b)\land(a\lor\neg b)
aa 与 bb 取值不同 (a∨b)∧(¬a∨¬b)(a\lor b)\land(\neg a\lor\neg b)

更一般地,禁止两个布尔变量取某一种特定的联合赋值,只需要一个子句。例如,禁止 x=truex=\mathrm{true} 与 y=falsey=\mathrm{false} 同时成立,就得到 ¬x∨y\neg x\lor y。因此,任何至多涉及两个变量的布尔关系,都可以通过排除其不允许的赋值来表达。

应用

这种编码方式使 2-SAT 可用于二选一的可行性问题:

  • **配置:**某些选项可能要求同时启用其他选项,也可能彼此不兼容。
  • **受限调度:**每个项目都有两种可能的安排,并且禁止同时采用不兼容的安排组合。
  • **几何标注:**每个标签有两个候选位置,发生重叠的两个位置不能同时选用。
  • **程序分析与验证:**在更广泛的形式验证过程中,某些布尔蕴含约束系统可以作为 2-SAT 实例求解。

这些限制至关重要。调度或配置问题并不会仅仅因为包含布尔决策就自动成为 2-SAT 问题;所有必需的约束都必须能够进行适当的编码。

复杂性与相关问题

与一般 SAT 的比较

不受限制的 SAT 和 3-SAT 都是 NP完全的,而 2-SAT 可以在多项式时间内求解;更具体地说,其求解时间相对于显式输入的大小是线性的。因此,允许每个子句含有第三个文字,就跨越了一条重要的复杂性边界。

这并不意味着每个长度为三的子句都能通过引入辅助变量,转换成等价的 2-SAT 构造。如果存在从 3-SAT 到 2-SAT 的一般性多项式时间归约,就意味着P与NP问题得到了肯定答案。

从更精细的角度看,在对数空间多对一归约下,2-SAT 是 NL 完全的;NL 是可用非确定性对数工作空间求解的判定问题所构成的复杂性类。这一分类关注的是内存受限的计算,与 2-SAT 存在线性时间算法并不矛盾。

满足赋值的计数

#2-SAT 询问一个 2-CNF 公式有多少个满足赋值。尽管判定是否至少存在一个满足赋值是易解的,但该计数问题却是 #P完全的。

通过无向图中的独立集可以看出这一区别。为每个顶点引入一个变量 xvx_v,并为每条边 {u,v}\{u,v\} 添加子句

¬xu∨¬xv.\neg x_u\lor\neg x_v.

满足赋值恰好对应于不含任何相邻顶点对的顶点子集。统计这些子集的数量是一个困难的计数问题,尽管只要将所有变量都设为假,就总能满足该公式。

最大化与附加要求

MAX-2-SAT 要求找到一个赋值,使得到满足的子句尽可能多。与普通的 2-SAT 不同,它是 NP难的。

附加要求同样可能使问题不再易解。例如,在上述独立集编码中,最大化真值变量的数量,恰好就是最大独立集问题。因此,线性时间可满足性算法并不能自动扩展为在满足赋值中进行数学优化的算法。

结构性局限

2-CNF 公式描述的是一类特殊的布尔关系,通常称为双合取关系。其满足赋值对逐坐标多数运算封闭:取三个满足赋值,对每个变量选取在其中至少两个赋值中出现的值,所得赋值仍然是满足赋值。

对于一个含两个文字的子句,如果多数运算得到的赋值使两个文字都为假,那么在原来的三个赋值中,每个文字都至少有两次为假。这两组赋值必然有交集,因此至少有一个原始赋值也会使两个文字同时为假,与其为满足赋值相矛盾。

这一性质解释了其表达能力的局限。关系

a∨b∨ca\lor b\lor c

对多数运算并不封闭:赋值 100100、010010 和 001001 都满足它,但它们逐坐标取多数得到的 000000 却不满足。因此,即使允许引入存在量化的辅助变量,也不能用 2-CNF 公式精确表示这种三者“至少一个为真”的关系。以存在量化方式消去变量会保持多数封闭性。