問題與假設
定義 6.1.1
(帶權 Max-2SAT)
布爾(Boolean)變量只能是真或假;文字是變量或其否定。只要一個子句中至少有一個文字為真,賦值便滿足該子句。這裏每個子句恰有兩個文字,且它們屬於不同的變量;每個子句的權重均為以二進制編碼的非負有理數。允許重複子句,並分別計算其權重。以 表示權重總和,以 表示所有賦值中所能滿足的最大權重。
我們要最大化滿足的權重;題目不保證全部子句可以同時滿足。
隨機賦值
把每個變量獨立、等概率地設為真或假。令 表示權重為 的第 個子句是否被滿足,則滿足的權重為 。
定理 6.1.2
(隨機賦值的期望權重)
在上述假設下,。因此必存在一個賦值,其滿足權重至少為 。
證明
(對各子句應用期望的線性性)
一個子句的兩個文字同時為假的概率是 ,因為它們屬於不同變量,而這些變量是相互獨立的公平位元。所以每個子句被滿足的概率是 ,由期望的線性性,
子句的指示變量可以相依,例如兩個子句可能共用變量;線性性不要求它們獨立。由權重非負,,因此 。特別地,必存在一個賦值的權重至少為 :否則有限個賦值的平均值便會更小。
利用條件期望去隨機化
定義 6.1.3
(部分賦值的條件期望)
對部分賦值 ,令 為其餘未定變量仍獨立等概率取值時的期望滿足權重。於是 ,而對完整賦值, 就是它的滿足權重。
定理 6.1.4
(確定性保證)
在上述假設下,存在確定性多項式時間算法,輸出滿足權重至少為 的賦值,因此亦至少達到 。
證明
(選取較好的分支不會降低條件期望)
逐個確定變量。對下一個變量 ,全期望公式給出
兩個條件期望中至少有一個不小於 。選取該值後繼續。起初 ;最後沒有隨機性, 就是實際滿足權重。因此數值從未低於初始期望。
每個 都逐個子句計算。已經為真的子句貢獻其全部權重 ;兩個文字都已定為假的子句貢獻 ;其餘情況下,子句中尚有 個不同變量未定,且沒有文字為真,貢獻為 ,即 或 。設有 個變量、 個子句,每一步計算兩個各含 項的和,所以整個過程對有理數作 次加法和乘法。它們的公分母整除權重公分母的四倍,因此位長仍是輸入大小的多項式。
證明透視
計算勢能,而不是猜測
不變量就是整個證明: 是兩個子分支的平均,所以必有一個不差於它的分支,而最後 就是實際權重。兩個細節使它由存在性的陳述變成算法。第一, 可以精確求值而無須列舉賦值,因為同一子句中未定變量與已定變量相互獨立:沒有文字為真、且有 個不同變量未定的子句,為假的概率恰為 。第二,相等時可任意取捨,因為論證只需要所選分支不小於平均值。不同變量這一假設在這裏同樣重要:若子句內重複出現某個變量, 就要數的是不同變量而不是文字。
例題詳解
例題 6.1.5
(逐步比較條件期望)
考慮權重為 的 、權重為 的 ,以及權重為 的 。此時 ,起初 。令 為真得到 ;令它為假得到 ,故選真。接著 為真給出 , 為假給出 ,故選假。最後令 為真可滿足全部子句,權重為 ;若為假則為 。每次選擇都保持或提高條件期望。
例題 6.1.6
(兩個分支相等的情況)
取權重各為 的 與 。此時 ,。令 為真得到 ,令它為假得到 :兩個分支相等,選哪一個都可以。取 為真。接著 為真給出 ,低於 ; 為假給出 ,故選假。最後權重為 ,大於起始值 ,在這裏也等於 。值較小的分支從不被選取,這正是數值不會下降的原因。
例題 6.1.7
(重複的子句分別計算)
取兩份 ,每份權重為 ,以及權重為 的 。此時 ,。令 為真得到 ;令它為假得到 ;兩者的平均是 ,與恆等式相符。選真。接著 為真給出 , 為假給出 。選假,最終權重為 。
結論的邊界
反例模式
為何需要兩個不同變量
對單一子句 ,滿足概率是 ,不是 ;它其實相當於單文字子句。若子句內變量重複或允許單文字子句,上面的推導不能直接照搬。負權重也會使 的比較失效。
常見錯誤
(把相對 的緊性當作比率 的緊性)
下界 可以剛好達到。取四個單位權重子句 、、 和 。每個賦值恰好使其中一個為假,因此每個賦值的值都是 。這裏 :例子說明相對 的界是緊的,並沒有說明相對 的 比率是緊的。
常見錯誤
(期望得到最優解,或把保證推廣到更長的子句)
這是對所述特例的保證,並非對任意子句長度的斷言,也不表示算法總能找到最優解。單次隨機賦值只在期望意義下有保證;確定性的保證來自條件選擇。
總結
均勻隨機賦值以概率 滿足每個由兩個不同變量構成的子句,因此期望權重為 。逐個確定變量並始終保留條件期望較大的分支,不會降低這個值,由此得到權重至少為 的確定性多項式時間賦值。
練習
快速檢查
(在獨立公平賦值下,求兩個不同變量構成的 被滿足的概率。)
解答 · 答案
只有 為真且 為假時兩個文字同時為假,概率為 ;答案是 。
快速檢查
(在第一個例題中,解釋為何 為假時的條件值是 。)
解答 · 答案
第一個子句貢獻 ,第二個貢獻 ,第三個貢獻 ;總和為 。
快速檢查
(部分賦值已使某子句的兩個文字均為假時,它對 的貢獻是多少?若子句已為真呢?)
解答 · 答案
分別為零及該子句的全部權重,因為後續賦值不會改變這兩種結果。
快速檢查
(為何四子句例子不能證明相對 的比率 是緊的?)
解答 · 答案
其最優值是 ,而每個賦值都達到 ,故相對最優值的比率是 ,雖然其值是 。