为什么限制为两个文字很重要
子句 (¬p∨q) 表示:只要 p 为真,q 就必须为真。当每个子句至多含两个文字时,每个子句都能写成单个文字之间的蕴含。把这些蕴含连成有向图,路径就记录了一连串被迫作出的选择。这使 2-SAT 成为可满足性、图算法与空间复杂度三者的交汇点。
我们将证明可满足性的一个判据,并用它把这个问题放入 NL。困难性论证则朝相反方向进行:它把任意的有向可达性实例转换成子句。这个结果并不表示 NL 等于 L;确定性对数空间是否足以判定 2-SAT,与尚未解决的 L 对 NL 问题密切相关。
公式与蕴含图
文字是变量 x 或其否定 ¬x;用 aˉ 表示文字 a 的相反文字,因此 ¬x=x。2-CNF 公式是每个子句含一个或两个文字的合取式。空合取为真;如果输入明确含空子句,公式为假,可先单独处理。输入显式列出变量及子句,变量有互不相同的二进制编号,子句只引用表内变量;因此变量数不超过输入长度。格式不合法时拒绝。构图时把单位子句 (a) 当成 (a∨a)。
每个变量对应顶点 x,¬x。每个子句 (a∨b) 给出两条边
aˉ⟶b,bˉ⟶a.该子句等价于这两个蕴含;单位子句给出边 aˉ→a。
若有从 a 到 b 的路径,任何满足公式且令 a 为真的赋值都必须令 b 为真。允许长度为零的路径,但它不会把一个变量连到与之不同的否定文字。
概念视角结构
满足赋值就是对边封闭的文字集合
赋值对应于它的真文字集合 T,其中每个变量恰含 a,aˉ 之一。赋值满足公式,恰当 T 对边封闭:若 aˉ∈T 且子句 (a∨b) 出现,则 b∈T,对 bˉ 同理。所以,满足赋值就是蕴含图中一致且对后继封闭的文字集合。
设 F=(¬p∨q)∧(¬q∨r)∧(¬r)。图中有 p→q→r→¬r,其后接着 ¬r→¬q→¬p。因此,选择 p 为真会同时迫使 r 与 ¬r 为真。这并不使公式不可满足:p=q=r=false 满足全部子句。从 p 到 ¬p 的单向路径只排除 p=true,并不排除 p 的两个取值。
可满足性判据
有向图中的两个顶点属于同一个强连通分量,当且仅当它们互相可达。把每个分量缩成一个顶点,得到无环的缩点图。分量的拓扑顺序是一种排列,使不同分量之间的每条边都由较前的分量指向较后的分量。
不含空子句的 2-CNF 公式可满足,当且仅当不存在变量 x 使得蕴含图同时有路径 x⇝¬x 和 ¬x⇝x。
先看必要性。若两条路径都存在,任何赋值都必须令 x,¬x 中恰好一个为真;从真文字出发沿路径传播,就迫使另一个也为真,矛盾。
证明充分性时,取分量的一个拓扑顺序。假设每个文字与其相反文字处于不同分量,令 a 为真,当且仅当 a 的分量比 aˉ 的分量更晚。两者位置不同,故恰有一个为真,这确实给每个变量指定了一个值。
若子句 (a∨b) 为假,令 C(v) 为文字 v 所在分量的次序。根据赋值规则,C(a)<C(aˉ) 且 C(b)<C(bˉ);两条蕴含边又给出 C(aˉ)≤C(b) 和 C(bˉ)≤C(a)。于是
C(a)<C(aˉ)≤C(b)<C(bˉ)≤C(a),矛盾。因此所有子句都为真,重复文字的单位子句也包括在内。
证明透视
假设在哪里使用,不等式链如何闭合
假设只用了一次。两条路径 x⇝¬x 与 ¬x⇝x 同时存在,恰好表示 x 与 ¬x 在同一个分量;假设不成立才使两者位置不同,“较后的分量为真”才是良定义的规则。关键一步是不等式链:子句为假提供两个严格不等式,子句本身的两条边提供两个非严格不等式,因为在拓扑顺序中边不会指向较前的分量。这条链回到 C(a),即得出 C(a)<C(a)。若去掉假设,对于与自己的否定同属一个分量的文字,规则就无从比较,例如 (p)∧(¬p)。相比之下,必要性既不用分量也不用顺序,只是沿路径传递被迫的取值。
单位子句 (p) 和 (¬p) 分别给出 ¬p→p 与 p→¬p。两个文字互相可达,所以公式不可满足;加入更多子句也不能消除这两条路径。
下面的互动图为 2-CNF 公式构造蕴含图,逐个变量列出两个方向的路径,并逐个子句检查由分量次序得到的赋值。
蕴含图的对称性与如何读出赋值
可满足性判据说明:2-CNF 公式可满足,当且仅当没有文字与其否定属于同一个强连通分量。上面的构造利用了蕴含图关于否定的对称性。本节直接证明这一对称性,再解释为什么赋值规则要比较互补的分量,以及为什么选择“较后”而非“较前”的分量。
以下用 ℓ 表示 ¬ℓ,所以 ℓ=ℓ。单位子句 (a) 当作 (a∨a) 处理。
边集自带逆否对称性
如果 a→b 是蕴含图的一条边,那么 b→a 也是一条边。
每条边都来自某个子句 (x∨y),该子句给出两条边 x→y 和 y→x。假设 a→b 是第一条,即 a=x、b=y,那么
b→a=y→x,这正是同一子句给出的第二条边。若 a→b 是第二条边,论证对称。对单位子句 (x),有 x=y,两条边重合为 x→x;它的逆否边是 x→x=x→x,也就是它自身。重复的子句只会给出已有的边。每个子句给出的边集都具有这种对称性,因而整个边集也具有这种对称性。
若 ℓ0→ℓ1→⋯→ℓk 是一条路径,那么 ℓk→ℓk−1→⋯→ℓ0 也是路径。
对路径的每条边应用上面的引理,再将所得边倒序排列,便得到结论。特别地,u⇝v 当且仅当 v⇝u。
互补的强连通分量
对于强连通分量 C,定义 C={ℓ:ℓ∈C}。
C 也是强连通分量。映射 C↦C 作用两次后回到原分量;在缩点图中,C⇝D 当且仅当 D⇝C。
首先,C 是强连通的。任取 x,y∈C,其中 x,y∈C。由于 y⇝x,路径反转给出 x⇝y;同理也有 y⇝x。
其次,C 是极大的。设 D 是包含 C 的强连通分量。由上一步,D 强连通,且包含 C=C。由于 C 已是整个强连通分量,D⊆C,因此 D⊆C。于是 D=C。
由 ℓ=ℓ 得到 C=C。对 C 和 D 中的代表文字应用路径反转,即得到可达性的结论。
两个强连通分量要么相等,要么不相交。因此,每个 C 恰好属于以下两种情况之一:
- C=C: 此时 C∩C=∅,分量与其互补分量配成一对。
- C=C: 此时每个 ℓ∈C 都满足 ℓ∈C,这正是公式不可满足的情形。反过来,若 x 和 x 同属分量 C,则 x∈C∩C,所以 C=C。
第二种情况并未被任何互异性假设排除;即使只有一个变量,也可能发生,下面第一道练习便是例子。
为什么比较配对分量,又为什么选“较后”
拓扑顺序只是分量的一张列表,本身并未指定哪些文字为真。有效赋值必须令 ℓ,ℓ 恰有一个为真,所以规则必须共同决定每一对 {C,C}。
反例模式
令顺序后半部分为真
一个诱人的规则是令拓扑顺序后半部分的所有文字为真。这个规则忽略了配对,因而会失败。考虑变量为 p,q 的公式 (p)。图中唯一的边是 p→p,故四个分量分别是单点 p,p,q,q。顺序 q,q,p,p 是拓扑顺序,因为唯一的限制是 p 在 p 前面。其后半部分是 p,p;把两者都判为真,根本不能构成赋值。
前面的规则比较的则是 C 与 C 的位置。当 C=C 时,两者位置不同,所以恰有一个在后面。
为什么选较后而非较前。 假设 ℓ⇝ℓ。如果 ℓ 为真,那么 ℓ 也必须为真,这是不可能的。因此这条路径迫使 ℓ 为假。单凭这条路径只能强制一个取值,并不足以证明公式不可满足,也不足以证明整个公式可满足;若还有反向路径 ℓ⇝ℓ,这对文字就产生矛盾。此外,另一个变量也可能导致公式不可满足。
如果两个分量不同,这条路径使 ℓ 的分量在每个拓扑顺序中都排在 ℓ 的分量之前;如果两者重合,判据说明公式不可满足。因此,在两个分量不同的情况下,“较后”规则令 ℓ 为真,与上述强制关系一致。
“较前”规则则不一致。对于只有子句 (p) 的公式,唯一的边 p→p 给出唯一顺序 p,p。
- “较后”规则令 p 为真,满足 (p)。
- “较前”规则令 p 为真,于是 p 为假,子句不成立。
令 F=(¬p∨q)∧(¬q∨r)∧(¬r)。各子句给出的边如下:
- (¬p∨q) 给出 p→q 和 q→p。
- (¬q∨r) 给出 q→r 和 r→q。
- (¬r) 给出 r→r,它的逆否边就是自身。
这五条边组成一条路径:
p→q→r→r→q→p.图中没有环,故六个分量都是单点,任何文字也不会与自身的相反文字同属一个分量。由于这条链经过所有顶点,唯一的拓扑顺序是 p,q,r,r,q,p,位置依次为 1 至 6。
逐对比较位置:
- p 在位置 1,p 在位置 6,所以 p 为假。
- q 在位置 2,q 在位置 5,所以 q 为假。
- r 在位置 3,r 在位置 4,所以 r 为假。
在 p=q=r=false 下逐个检查子句:
- ¬p∨q 成立,因为 ¬p 为真。
- ¬q∨r 成立,因为 ¬q 为真。
- ¬r 为真。
令变量为 p,q,r,并取 G=(¬p∨q)∧(¬q∨p)∧(r)。其边为
p→q,q→p,q→p,p→q,r→r.强连通分量是 {p,q}、{p,q}、{r} 和 {r}。正如互补分量引理所述,{p,q}={p,q}。分量间唯一的边是 {r}→{r}。
选择顺序 {p,q},{p,q},{r},{r}。它是有效的拓扑顺序,因为 {r} 在 {r} 前面。
- {p,q} 在其互补分量之后,所以 p=q=true。
- {r} 在 {r} 之后,所以 r=true。
检查各子句:
- ¬p∨q 因 q 为真而成立。
- ¬q∨p 因 p 为真而成立。
- r 为真。
交换前两个分量,仍得到有效的拓扑顺序,此时 p=q=false、r=true,也满足公式。不同的拓扑顺序不一定产生相同的赋值;定理只断言每个顺序都能产生某个满足赋值。
练习
练习 3.6.12
(分析 (p)∧(¬p):求出它的强连通分量,并判定是否可满足。)
核心
解答(4)
1读出各条边
子句 (p) 给出边 p→p,(¬p) 给出边 p→p。
2找出强连通分量
这两条边构成环,所以只有一个分量 C={p,p},且 C=C。
3比较位置
唯一的拓扑顺序是只有一项的列表 C。它的互补分量占据同一位置,因此比较规则无法决定 p;判据说明公式不可满足。
4直接检查
p=true 违反 (¬p),而 p=false 违反 (p)。
练习 3.6.13
(证明 (¬p∨q)∧(¬q∨p) 既允许 p=q=false,也允许 p=q=true。)
核心
解答(4)
1列出边与强连通分量
边为 p→q、q→p、q→p 和 p→q。两个分量是 {p,q} 和 {p,q},它们之间没有边,所以两种排列都是拓扑顺序。
2读出第一种顺序
对顺序 {p,q},{p,q},否定文字所在分量较后,因此 p=q=false。两个子句分别由 ¬p 和 ¬q 满足。
3读出第二种顺序
对顺序 {p,q},{p,q},得到 p=q=true。两个子句分别由 q 和 p 满足。
4排除真假混合的赋值
p=true、q=false 时第一子句为假;p=false、q=true 时第二子句为假。这与图一致:p 和 q 属于同一个分量,所以它们被迫取相同的值。
2-UNSAT 与 2-SAT 属于 NL
令 2-UNSAT 为格式正确且不可满足的 2-CNF 公式所组成的语言,格式错误的字符串拒绝。非确定性对数空间机器先检查编码;有空子句时立即接受,否则猜一个变量 x,猜从 x 到 ¬x 的路径,再猜反向路径。若图有 N 个文字顶点,存在路径时必有至多 N−1 条边的简单路径。机器只需保存选定变量、当前顶点及一个 O(logN) 位计数器;用文字在显式变量表中的位置及一个符号位来保存它,而不必复制可能很长的二进制编号;要检查某条猜测的边,只需重扫变量表和子句表。因此两次路径搜索都只用 O(logn) 个工作比特,其中 n 为输入长度。两次搜索在同一计算分支上依次进行,必须对同一个变量都成功。
由判据,机器恰好接受 2-UNSAT。由 NL=coNL,其普通补集也属于 NL;再用确定性对数空间格式检查排除非法编码,得到由格式正确且可满足的公式组成的 2-SAT。因此两种语言均属于 NL。
不能通过简单交换非确定性机器的接受和拒绝状态来证明补集封闭:同一输入可以同时存在接受分支和拒绝分支,交换后的机器对这个输入仍然接受。这里要用的是 NL=coNL。
从可达性归约
定理 3.6.14
(2-SAT 与 2-UNSAT 的 NL 完全性)
对于以上显式编码,2-SAT 和 2-UNSAT 都在确定性对数空间多对一归约下为 NL 完全。
给定有向图 G=(V,E) 和指定顶点 s,t,为每个顶点建立变量 xv,输出单位子句 (xs)、(¬xt),并为每条边 u→v 输出
(¬xu∨xv).
如果 s 可达 t,第一个单位子句沿路径迫使 xt 为真,与第二个单位子句矛盾。反过来,若 t 不可达,令恰好从 s 可达的顶点对应变量为真。两个单位子句成立;而从可达顶点出发的边必到达可达顶点,所以每个边子句也成立。这里的可达集合只用于证明存在赋值,不要求归约算法算出该集合。
归约用顶点编号和重复扫描逐个输出子句,无需保存整张输出公式或任何可达集合,工作空间为对数,输出长度为多项式。若 s=t,两个单位子句直接冲突,与长度零路径相符。因此 STCON 归约到 2-UNSAT,后者是 NL 困难的。
为证明 2-SAT 困难,任取 A∈NL。由 NL=coNL,A 属于 NL,故可对数空间归约到 STCON。再复合上述构造:所得公式可满足当且仅当对应图中不存在路径,亦即原输入属于 A。使用对数空间归约的标准复合性质,得到对 2-SAT 的归约。结合上面的成员性,两项完全性都得到证明。
由 (G,s,t) 构造的公式可满足,当且仅当 t 从 s 不可达。因此它直接把 STCON 归约到 2-UNSAT。若把它当成 STCON 到 2-SAT 的归约就错了:那需要的是 STCON 的补问题,而这正是 NL=coNL 发挥作用的地方。
图中边为 1→2、2→3,取 s=1,t=3,所得公式为
(x1)∧(¬x3)∧(¬x1∨x2)∧(¬x2∨x3).第一项和两个边子句依次迫使 x2,x3 为真,与第二项冲突。若删去第二条边,则 x1=x2=true、x3=false 满足剩余公式。
练习与解答
快速检查
((p∨q)∧(¬p∨q)∧(¬q) 可满足吗?)
解答 · 答案
不可满足。第三项要求 q 为假,此时前两项分别要求 p 和 ¬p 为真。等价地,蕴含图中 p 与 ¬p 之间两个方向都有路径。
快速检查
(给出有路径 p⇝¬p 但可满足的公式。)
解答 · 答案
单位子句 (¬p) 有边 p→¬p,取 p 为假即可;反向路径不存在。
快速检查
(图中 t 从 s 不可达时,如何满足归约得到的公式?)
解答 · 答案
恰好令从 s 可达的顶点为真。可达集合不会有边指向其补集,因此边子句及两个单位子句均成立。
解答 · 答案
保留选定变量,每次只存当前文字和有界计数器;先完成一条路径,再重用空间搜索反向路径,不必保存整条路径。
快速检查
(上面的证明是否给出确定性对数空间 2-SAT 算法?)
解答 · 答案
没有。证明用了非确定性可达性及 NL=coNL;若有这样的确定性算法,结合困难性归约便有 L=NL。