為甚麼限制為兩個文字很重要
子句 (¬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 必定不同,所以不能排除第二種情況。即使只有一個變量,第二種情況也可能發生,下面的第一道練習就是一個例子。
為何要比較配對分量,以及為何選「較後」
拓撲順序只是一張分量的排列清單,本身並沒有指定哪些文字為真。合法賦值必須令 ℓ,ℓ 中恰好一個為真,所以任何賦值規則都必須把每對 {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=假 代入,逐一檢查子句:
- ¬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=真。
- {r} 比 {r} 較後,所以 r=真。
逐一檢查子句:
- ¬p∨q 因 q 為真而成立。
- ¬q∨p 因 p 為真而成立。
- r 為真。
交換前兩個分量,仍然得到合法的拓撲順序。此時規則給出 p=q=假、r=真,同樣滿足公式。不同的拓撲順序不一定產生相同賦值;定理只保證每個拓撲順序都能產生某個滿足公式的賦值。
練習
練習 3.6.12
(分析 (p)∧(¬p):求出它的強連通分量,並判定是否可滿足。)
核心
解答(4)
1讀出各條邊
子句 (p) 給出邊 p→p,而 (¬p) 給出邊 p→p。
2找出強連通分量
兩條邊形成有向環,所以只有一個強連通分量 C={p,p},並且 C=C。
3比較位置
唯一的拓撲順序是只含一項的清單 C。它的配對分量就是自己,位置相同,所以比較位置的規則無法為 p 選值;可滿足性判據則判定公式不可滿足。
4直接檢查
p=真 違反 (¬p),而 p=假 違反 (p)。
練習 3.6.13
(證明 (¬p∨q)∧(¬q∨p) 同時容許 p=q=假 和 p=q=真。)
核心
解答(4)
1列出邊與強連通分量
圖中的邊是 p→q、q→p、q→p 和 p→q。強連通分量是 {p,q} 和 {p,q},不同分量之間沒有邊,所以兩種排列都是拓撲順序。
2讀出第一種順序
對順序 {p,q},{p,q},否定文字所在的分量較後,所以 p=q=假。兩個子句分別因 ¬p 和 ¬q 為真而成立。
3讀出第二種順序
對順序 {p,q},{p,q},得到 p=q=真。兩個子句分別因 q 和 p 為真而成立。
4排除真假混合的賦值
若 p=真、q=假,第一個子句為假;若 p=假、q=真,第二個子句為假。這與圖的結構一致: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。