動機
CNF 公式可能不可滿足,但我們仍然可以尋求一個盡可能多地滿足公式的賦值。在帶權 MAX-SAT 中,每個子句帶有一個非負權重,目標是使被滿足子句的總權重最大。隨機賦值提供一個簡單的基線:每個非空子句被滿足的概率至少為二分之一。
這個期望論證亦導出一個確定性算法。逐個固定變量,每次選取一個不會令最終得分的條件期望下降的取值。這是條件期望法的一個例子:概率性的存在性證明變成了一連串明確的選擇。
定義
定義 6.7.1
(帶權 MAX-SAT 實例與得分)
輸入是布爾(Boolean)變量上的有限子句列表,以及非負有理權重 。子句是文字出現的析取。若子句中至少有一個文字為真,則其得分等於其權重,否則得分為零。一個賦值的得分是所有被滿足子句的權重之和, 是所有賦值中的最大得分。
同時含有 與 的子句稱為重言子句,它總是被滿足。同一文字的重複出現不會改變子句的真值;計算相異變量個數時應去除重複。空子句總是為假。在主要定理中,我們假設每個非重言子句都非空;空子句對任何賦值的貢獻均為零,故可以刪去。
定義 6.7.2
(均勻隨機賦值與總權重)
讓每個變量獨立且均勻地取假或真。令 ,求和範圍為所有非空子句(包括重言子句)。在主要假設下,它是 的一個上界。
定理
定理 6.7.3
(二分之一近似)
對於權重非負且不含空子句的帶權 MAX-SAT,均勻隨機賦值的期望得分至少為 。一個確定性的多項式時間條件期望算法所得的得分至少為 。
定理 6.7.4
(恰好三個文字時的改進)
若每個子句恰好含有三個文字,且這三個文字屬於三個相異變量,並且沒有子句是重言子句,則同樣的隨機賦值的期望得分為 。條件期望法可得到一個確定性賦值,其得分至少為 。
證明
得分的期望
證明
(均勻賦值的期望得分)
含有 個相異變量的非重言子句為假,當且僅當其每個文字都為假。這些相異變量所需的取值互相獨立,所以子句為假的概率是 ,被滿足的概率是 。重言子句被滿足的概率為一。
令 為子句 被滿足的指示變量。它的加權期望貢獻是 。由期望的線性性,
各子句的指示變量不必互相獨立:不同子句可以共用變量。線性性並不要求它們互相獨立。權重非負,確保把每個滿足概率換成其下界後不等式仍然成立。由於沒有任何賦值的得分能超過 ,所以這個值至少為 。
當每個子句恰好含有三個相異變量且不是重言子句時,其為假的概率恰為 。每個子句被滿足的概率都是 ,所以期望總得分恰為 。同樣的上界 給出近似保證。這個值是期望值;個別賦值的得分可能較低,也可能較高。
證明透視
獨立性只用在子句之內
這裏結合了兩種概率推理,其中只有一種需要獨立性。在單個子句之內,相異變量的公平位元相互獨立,因此子句為假的概率恰為 :使其為假的賦值把 個變量各定為一個值,概率相乘。重複的變量會破壞這一點,因為這時各文字並不獨立;子句 為假的概率是 ,而不是 。在各子句之間只用到期望的線性性,它對指示變量之間的任何相依關係都成立,所以共用變量不構成代價。非負權重在最後一步起作用:把每個 換成下界 ,只有在每個權重都非負時才保持不等式。
用條件期望去隨機化
證明
(條件期望永不下降)
按任意固定的次序處理變量。假設已有一些變量被固定。計算在下一個變量取假、其餘變量仍保持均勻隨機時最終得分的期望;同樣計算該變量取真時的期望。當前的條件期望是這兩個數的平均值,因為下一個變量仍是一個公平的獨立位元。至少有一種取法,其條件期望不小於當前值。把變量固定為這樣的取值(若相等則任選),然後重複這一步驟。
所有變量都被固定之後,不再有任何隨機性。此時的條件期望就是所構造賦值的實際得分。它不小於最初的期望,這就證明了兩個確定性保證。
這兩個期望可以由子句直接算出。已被滿足的子句貢獻其全部權重。若一個子句的已固定文字全部為假,且還有 個未賦值的相異變量,則當 時它貢獻 ,當 時貢獻零。重言子句貢獻其全部權重。這些量都是有理數,可以精確求和。若有理輸入權重以二進制表示,則直接通分並重複掃描子句,所用的位數與運算次數都是多項式的;2 的冪因子的指數至多為變量個數。
例題詳解
例題 6.7.5
(單個子句)
對於無權子句 ,八個賦值中恰有一個令三個文字全為假。均勻賦值的期望得分是 。最優值為一,任何至少有一個變量為真的賦值都能達到它。
例題 6.7.6
(一次條件選擇)
對於兩個無權子句 與 ,初始期望得分為 。令 為真,期望得分為 ;令 為假,則為 。條件期望法選擇 。接著它選擇 ,最終得分為二。
例題 6.7.7
(相反的單位子句)
對於權重各為一的 與 ,每個賦值都恰好滿足一個子句。期望得分為一,最優值也為一。上界 並不總是可以達到,所以用 作的近似證明可能偏保守。
例題 6.7.8
(重複的文字不增加隨機性)
子句 在 為假時為假,概率是 ,而不是 。去掉重複後它就是一個單位子句。它不符合 結論中「恰好三個相異變量」的假設。
常見錯誤
反例模式
期望不是對每一次運行的保證
對於單個子句 ,隨機賦值的期望得分是 ,但賦值 的得分為零。確定性的條件期望過程選取的是條件期望得分足夠高的取值;而一次未經檢驗的隨機運行不一定能達到該期望。
常見錯誤
(數文字出現次數而不是相異變量)
因子 要求每個子句含有三個相異變量。若某個變量重複出現,三個文字出現次數並不足夠。重言子句總是被滿足,可以單獨處理,但其滿足概率是一,而不是恰好 。
常見錯誤
(忽略權重的符號)
非負權重十分重要。若某個子句的權重為負,提高滿足該子句的機會反而可能降低得分,而且 亦不再以同樣的方式成為最優值的上界。該定理不涵蓋負權重。
理解確定性的選擇
部分賦值把每個非重言子句分成三種情形。若某個已固定的文字為真,則該子句必然有貢獻。若所有文字都已固定為假,則它不可能有貢獻。否則,已固定的文字全為假,餘下的相異變量必須全部取各自唯一的使文字為假的值,子句才會失敗。這就給出了算法所用的條件貢獻。
條件期望並不是靠猜測未來來估計某個貪心賦值最終的得分。它是對其餘變量所有補全方式取平均。下一個變量的兩個分支把這些補全分成概率相等的兩半,所以其中一個分支的平均值不小於當前的平均值。重複這一論證,就能保證所保證的值不會下降。
權重和子句都可以重複。它們的貢獻按輸入列表的規定分別計數。共用變量令子句之間產生依賴,但由期望的線性性,逐個計算條件貢獻再求和仍然成立。
何時達到 的界
取三個變量 ,並包含所有八個子句,它們由獨立地選擇每個變量以正文字還是負文字出現得到。每個子句的權重為一。每個子句含有三個相異變量,且 。
對任意賦值,八個子句中恰有一個為假:在每個位置選取該賦值令其為假的文字即可。其餘七個子句都被滿足。因此每個賦值的得分都是七,最優值是七,而隨機賦值的期望得分恰為 。這個例子說明,在恰好三個文字的假設下,對均勻隨機賦值而言,相對於總子句權重的保證一般無法改進。它並不說明相對於最優值的近似比是 ,因為這裏每個賦值都是最優的。
概念視角組合
數一數使子句為假的賦值
期望也可以看成計數。含 個相異變量的非重言子句,在 個變量的 個賦值中恰有 個使它為假,所以全體賦值的平均得分是 。在上面的例子中,八個子句各自恰被一個賦值弄假,而每個賦值恰好弄假一個子句,兩邊的數目剛好相符。
以 表示的保證與以 表示的保證,兩者的分別很有用。不等式 把前者轉化為後者,但當這些子句無法全部滿足時,這樣做會損失資訊。更精細的近似分析可以使用比總權重更好的 上界。
一個帶權的條件計算
考慮權重為二的子句 、權重為三的子句 和權重為一的子句 。起初它們的期望貢獻分別為 、 和 ,總和為 。若 為真,第一個子句貢獻二,第二個子句期望貢獻 ,第三個子句期望貢獻 ,總計四。若 為假,第一個子句貢獻零,第二個貢獻三,第三個期望貢獻 ,總計 。四與 的平均值確實是 。
選取 。然後若選 ,則前兩個子句被滿足,得分為五;若選 ,則第一和第三個子句被滿足,得分為三。算法選擇真,輸出得分五,超過了它的初始期望。這一計算沒有假設第二和第三個子句的指示變量互相獨立;它們的條件期望貢獻只是直接相加。
精確算術與輸入規模
對於部分賦值,冪 的分母,其二進制長度至多為一加上未賦值變量的個數。每個輸入權重是分子分母均為二進制的有理數。把各輸入分母相乘,得到的公分母的位長至多是它們位長之和。再包含所需的最大的 2 的冪,位長至多再增加變量個數。
因此,條件和的計算與比較可以用多項式位長的整數完成。樸素的實現可能對每個變量的兩種取值都重新掃描每個子句;這對於顯式輸入規模來說仍是多項式的。更高效的增量更新是可能的,但要證明存在多項式時間的去隨機化並不需要它們。
總結
均勻賦值滿足每個非空子句的概率至少為二分之一,滿足每個恰含三個相異變量的子句的概率為八分之七。條件期望法逐個固定變量,且不令期望總得分下降,從而在所述的非負權重模型下得到確定性的近似保證。
練習
快速檢查
(在均勻賦值下,含有四個相異變量的非重言子句為假的概率是多少?)
解答 · 答案
令四個文字全為假的賦值是唯一的,其概率為 ,所以滿足的概率是 。
快速檢查
(對於權重相等的子句 與 ,每個賦值的得分是多少?)
解答 · 答案
兩個子句中恰有一個被滿足,所以當每個權重為一時,得分為一。儘管總子句權重為二,最優值仍是一。
快速檢查
(為甚麼期望的證明不要求不同子句互相獨立?)
解答 · 答案
得分是子句指示變量之和。無論是否存在依賴,期望對有限和都可分配;只需要計算每個單獨子句的概率。
快速檢查
(為甚麼條件期望算法總能選出一個不令當前期望下降的取值?)
解答 · 答案
當前期望是取假分支與取真分支的條件期望的平均值。兩個實數中至少有一個不小於它們的平均值,所以選擇該分支不會令值下降。