信息学奥林匹克论文.pdfVIP

信息学奥林匹克论文 华中师大一附中 赵爽 1/3 2-SAT 解法浅析 华中师大一附中 赵爽 SAT 理论基础 ˆ B b ,b , ,b , , , , , , , 设 {1 2 n }为一个有限布尔变量集，B {b1 b2 bn =¬b1 ¬b2 ¬bn }。 ① ˆ ˆ ′ ′ ′ ′ ′ B B B ∈B 设B 是B 的非空子集，定义∨B ∨ b 。对于给定的 1, 2 , , m ，求B ，使得 b∈B′ ∨B ′ ∧ ∨B ′ ∧∧ ∨B ′ 1 ( ) ( ) ( ) 1 2 m 成立的问题，称为适定性(Satisfiability) 问题，简称SAT 。 特别的，对于给定的 B ′ ，如果 max B ′ k ，我们就把这个问题称为 k-适定性 { } { } m i i 1,2,,m 问题，简称k-SAT 。 可以证明，当k 2 时，k-SAT 是NP 完全的。下面我们要讨论的，是k 2 时的情况。 2-SAT ˆ 在 2-SAT 中，B 只有两种形式，一种是单个布尔变量′ x ∈B ，另一种是两个布尔变量 i ˆ , 的或：x ∨y (x y ∈B )。为了方便，我们先分析只存在后一种形式的情况。 ˆ G G 2n 2n 我们可以构造有向图 。 包含 个顶点，代表B 中的 个元素。我们的问题转化 G n 为从 中选出 个顶点，使其满足 2-SAT 的条件——当然，代表b 和¬b 的顶点不能同时 i i 被选择。下面我们分析一下Bi′ x =∨y 在图对应什