问题与假设
定义 6.1.1
(带权 Max-2SAT)
布尔(Boolean)变量只能是真或假;文字是变量或其否定。只要一个子句中至少有一个文字为真,赋值便满足该子句。这里每个子句恰有两个文字,且它们属于不同的变量;每个子句的权重均为以二进制编码的非负有理数。允许重复子句,并分别计算其权重。以 表示权重总和,以 表示所有赋值中所能满足的最大权重。
我们要最大化满足的权重;题目不保证全部子句可以同时满足。
随机赋值
把每个变量独立、等概率地设为真或假。令 表示权重为 的第 个子句是否被满足,则满足的权重为 。
定理 6.1.2
(随机赋值的期望权重)
在上述假设下,。因此必存在一个赋值,其满足权重至少为 。
证明
(对各子句应用期望的线性性)
一个子句的两个文字同时为假的概率是 ,因为它们属于不同变量,而这些变量是相互独立的公平比特。所以每个子句被满足的概率是 ,由期望的线性性,
子句的指示变量可以相依,例如两个子句可能共用变量;线性性不要求它们独立。由权重非负,,因此 。特别地,必存在一个赋值的权重至少为 :否则有限个赋值的平均值就会更小。
利用条件期望去随机化
定义 6.1.3
(部分赋值的条件期望)
对部分赋值 ,令 为其余未定变量仍独立等概率取值时的期望满足权重。于是 ,而对完整赋值, 就是它的满足权重。
定理 6.1.4
(确定性保证)
在上述假设下,存在确定性多项式时间算法,输出满足权重至少为 的赋值,因此也至少达到 。
证明
(选取较好的分支不会降低条件期望)
逐个确定变量。对下一个变量 ,全期望公式给出
两个条件期望中至少有一个不小于 。选取该值后继续。起初 ;最后没有随机性, 就是实际满足权重。因此数值从未低于初始期望。
每个 都逐个子句计算。已经为真的子句贡献其全部权重 ;两个文字都已定为假的子句贡献 ;其余情形下,子句中尚有 个不同变量未定,且没有文字为真,贡献为 ,即 或 。设有 个变量、 个子句,每一步计算两个各含 项的和,所以整个过程对有理数作 次加法和乘法。它们的公分母整除权重公分母的四倍,因此位长仍是输入规模的多项式。
证明透视
计算势能,而不是猜测
不变量就是整个证明: 是两个子分支的平均,所以必有一个不差于它的分支,而最后 就是实际权重。两个细节使它由存在性的陈述变成算法。第一, 可以精确求值而无须枚举赋值,因为同一子句中未定变量与已定变量相互独立:没有文字为真、且有 个不同变量未定的子句,为假的概率恰为 。第二,相等时可任意取舍,因为论证只需要所选分支不小于平均值。不同变量这一假设在这里同样重要:若子句内重复出现某个变量, 就要数的是不同变量而不是文字。
例题详解
例题 6.1.5
(逐步比较条件期望)
考虑权重为 的 、权重为 的 ,以及权重为 的 。此时 ,起初 。令 为真得到 ;令它为假得到 ,故选真。接着 为真给出 , 为假给出 ,故选假。最后令 为真可满足全部子句,权重为 ;若为假则为 。每次选择都保持或提高条件期望。
例题 6.1.6
(两个分支相等的情形)
取权重各为 的 与 。此时 ,。令 为真得到 ,令它为假得到 :两个分支相等,选哪一个都可以。取 为真。接着 为真给出 ,低于 ; 为假给出 ,故选假。最后权重为 ,大于起始值 ,在这里也等于 。值较小的分支从不被选取,这正是数值不会下降的原因。
例题 6.1.7
(重复的子句分别计算)
取两份 ,每份权重为 ,以及权重为 的 。此时 ,。令 为真得到 ;令它为假得到 ;两者的平均是 ,与恒等式相符。选真。接着 为真给出 , 为假给出 。选假,最终权重为 。
结论的边界
反例模式
为何需要两个不同变量
对单一子句 ,满足概率是 ,不是 ;它其实相当于单文字子句。若子句内变量重复或允许单文字子句,上面的推导不能直接照搬。负权重也会使 的比较失效。
常见错误
(把相对 的紧性当作比率 的紧性)
下界 可以恰好达到。取四个单位权重子句 、、 和 。每个赋值恰好使其中一个为假,因此每个赋值的值都是 。这里 :例子说明相对 的界是紧的,并没有说明相对 的 比率是紧的。
常见错误
(期望得到最优解,或把保证推广到更长的子句)
这是对所述特例的保证,并非对任意子句长度的断言,也不表示算法总能找到最优解。单次随机赋值只在期望意义下有保证;确定性的保证来自条件选择。
总结
均匀随机赋值以概率 满足每个由两个不同变量构成的子句,因此期望权重为 。逐个确定变量并始终保留条件期望较大的分支,不会降低这个值,由此得到权重至少为 的确定性多项式时间赋值。
练习
快速检查
(在独立公平赋值下,求两个不同变量构成的 被满足的概率。)
解答 · 答案
只有 为真且 为假时两个文字同时为假,概率为 ;答案是 。
快速检查
(在第一个例题中,解释为何 为假时的条件值是 。)
解答 · 答案
第一个子句贡献 ,第二个贡献 ,第三个贡献 ;总和为 。
快速检查
(部分赋值已使某子句的两个文字均为假时,它对 的贡献是多少?若子句已为真呢?)
解答 · 答案
分别为零及该子句的全部权重,因为后续赋值不会改变这两种结果。
快速检查
(为何四子句例子不能证明相对 的比率 是紧的?)
解答 · 答案
其最优值是 ,而每个赋值都达到 ,故相对最优值的比率是 ,虽然其值是 。