動機
一個多項式規模的電路可以多次重用同一個中間結果。普通公式是一棵樹:如果我們把每個被重用的結果都代換為完整的表達式,就可能不斷重複同樣的工作。這正是上一單元的驗證者電路與小規模可滿足性公式之間剩下的障礙。解決辦法是給每個中間值命名,並施加一個簡短的約束來說明這個名字的含義。
輔助變量並不需要在對新名字的每一種任意賦值下都保持原來的表達式;它們需要保持的是一致擴張的存在性。這一區別是歸約的核心。我們先編碼各個閘,再把長子句拆成三文字子句,並始終追蹤對每個新變量的存在量詞。結合上一單元的構造,這就證明了 SAT 與 3-SAT 的 Cook–Levin 結論,而不只是引用它們。
定義
定義 2.3.1
(文字、子句,以及語言 SAT 與 3-SAT)
文字是一個變量或其否定。子句是若干文字的析取;合取範式(CNF)公式是若干子句的合取。這裏的三 CNF 公式要求每個子句恰有三個文字出現,容許重複。因此 是容許的。若採用要求三個互不相同的變量的約定,則需要下面給出的額外短子句小工具;僅靠文字重複並不能滿足那種不同的約定。
我們對使用 AND、OR、NOT 及常量的顯式編碼布爾(Boolean)公式定義 SAT,對採用剛才所述的三 CNF 約定的公式定義 3-SAT。格式不合法的串是否定實例。兩個語言都屬於 NP,因為賦值的長度至多等於顯式描述的長度,並且可通過對公式求值來檢驗。空合取為真,空子句為假;我們在給出全函數歸約時處理這些情形。
定義 2.3.2
(等可滿足性)
兩個公式 與 稱為等可滿足的,如果其中一個有滿足賦值恰當另一個也有。我們的變換證明的是更強的逐輸入命題
這並不是說對 的每個選擇都有 。新變量表示一致的中間值,而不是額外的任意接受許可。
定理/命題
定理 2.3.3
(線性規模的閘編碼)
對於具有 個輸入變量、 個閘(由常量、二元 AND/OR 與一元 NOT 構成)的顯式編碼布爾電路,可以在多項式時間內構造一個 CNF 公式,其每個子句至多有三個文字,至多有 個變量。它至多有 個子句,並且對原輸入的每個賦值,當且僅當電路輸出一時,該公式有滿足的擴張。
定理 2.3.4
(SAT 與 3-SAT 是 NP 完全的)
在上述顯式公式編碼與重複文字約定之下,SAT 與 3-SAT 是 NP 完全的。此外,每個 CNF 公式都可以在多項式時間內轉化為等可滿足的三 CNF 公式。對每個需要新變量的閘或子句,分別使用新的變量。
證明思路
為閘的值命名,而不是複製它的整個過去
證明
(閘的關係與一致的值)
給每個閘一個自己的輸出變量 。它的來源線是已經為輸入位或較早閘的輸出命名的變量。對每種類型施加以下子句:
常量一閘有單位子句 ;常量零閘有單位子句 。再添加一個單位子句,為指定的輸出線命名,要求它為一。如果輸出直接是一條輸入線,就在最後的子句中使用該輸入變量。
每個閘的子句表達了其關係的兩個方向。對於 AND 閘,前兩個子句說明 迫使兩個輸入都為一;第三個說明若兩個輸入都為一,則 必須為一。對於 OR 閘,前兩個子句在任一輸入為一時迫使 ,而第三個禁止兩個輸入都為零時 。NOT 子句迫使取相反的值。這些檢驗對所有布爾輸入都證明了這些關係,而不只是針對某個成功的例子。
給定一個輸入賦值,對電路求值就為每個閘提供了一組一致的值。這些值滿足所有定義子句,並且恰當電路接受時才滿足最後的單位子句。反過來,對全部變量的任何滿足賦值都滿足每個閘的關係。按拓撲順序做歸納,迫使每個閘變量等於其真實的求值結果。於是最後的單位子句使電路輸出為一。事實上,在施加輸出為一的要求之前,一致的擴張是唯一的。
每個閘至多有一個新變量,至多三個子句,再加上輸出子句。每個子句的寬度有界。讀取閘列表並寫出相應的固定模式需要多項式時間,其中包括用作變量名的二進制下標。這一變換通過反覆引用共享線的名字來保持共享,而不是反覆展開其表達式。
概念視角代數
把閘的關係寫成雙元素域上的方程
在 上,三種閘的關係就是方程: 對應 , 對應 , 對應 。逐一檢查 的八種賦值與 的四種賦值可知,上面每組子句恰在相應方程成立時被滿足。於是電路變成一個次數至多為二的方程組,每個閘對應一條方程。
用鏈替換長析取
證明
(以鏈替換長子句)
對於子句 (),引入互不相同的新變量 ,並把它替換為
當 時中間的合取為空,只剩兩個子句。若原來的每個文字都為假,則第一個子句迫使 ,中間的子句依次迫使此後每個 ,而最後一個子句為假。因此鏈被滿足就意味著原文字中至少有一個為真。
反過來,若原子句為真,則當且僅當 全為假時令 。第一個子句由此規則成立。在中間子句裏,若 ,其否定已滿足該子句;若 ,則下一個文字為真,或者下一個前綴仍為假且 。在最後的子句中,要麼其前綴標誌為零,要麼最後兩個文字之一為真。所以該鏈有滿足的擴張。這就證明了逐賦值的存在性等價。
證明透視
鏈的兩個方向各用到甚麼
連結變量 可以理解為一項義務:前 個文字都已失敗,因此後面的文字仍必須滿足原子句。兩個方向用到的東西不同。可靠方向(鏈被滿足則原子句為真)是一個向前的歸納:若每個 都為假,第一個子句迫使 ,其後每個中間子句 又迫使 ,直至最後一個子句不成立。完備方向按義務規則定義 ,並對每個子句檢查一次,分 與 兩種情形。不顯而易見之處在於:約束只需容許一致的義務,而不必迫使其唯一,因此可以有多個延拓。同時處理多個子句時,用到的假設是 的全新性:兩個子句共用同一個連結變量,可能同時被要求為 與 ,下面的第三個例題正說明這一點。
長度為一或二的子句可通過重複某個文字來補足。空子句使整個輸入為假,所以輸出一個固定的不可滿足三 CNF,例如 。空合取則可改為送到一個固定的重言子句。把格式錯誤的輸入串送到該固定的不可滿足公式。長度為 的長子句使用 個新變量和 個新子句。對顯式列出的出現求和,除多項式的命名開銷之外,新符號的數量是線性的。不同子句之間的新變量互不相同,保證它們的滿足擴張可以一起選取。
反例模式
鏈並非對每個連結值都等於原子句
聲稱: 的鏈 對 的每個值都與該子句有相同的真值。取 、,此時子句為真。 時鏈為真,但 時第二個子句是 ,鏈便為假。成立的陳述是存在式的:有某個 的值可行。這就是定義要求 而不是等式的原因。
若要求三個互不相同的變量
另一種常見的約定同樣可以做到。先刪去子句中文字的重複副本。同時含有某變量及其否定的子句是重言式,可以丟棄。經過這種化簡後,子句中不同的文字出現對應不同的底層變量。於是長子句鏈的每個新子句已有三個互不相同的變量,因為每個連結變量都是新的。
對於雙文字子句 ,引入新變量 並使用 。若原子句為真,則無論 取何值,兩個子句都成立。若它為假,兩個子句要求 同時取兩個值,矛盾。對於單位子句 ,使用兩個新變量 及四個子句 、、 和 。 為真時全部四個都滿足; 為假時,對 的每個賦值都會使其中一個子句為假。這些同樣是存在性擴張等價。
空子句可以表示為三個新變量上全部八種三文字符號模式的合取。每個賦值都會使這八個子句之一為假,所以它們的合取不可滿足。對於為真的空合取,輸出一個可滿足的三變量子句。所有這些替換對每個短子句只使用有界個新變量,保持了多項式規模界。因此要求互不相同變量的變體同樣是 NP 完全的。規定子句約定使證明變得精確;這些小工具則說明為甚麼這兩種約定具有相同的複雜度分類。
證明
(由電路可滿足性得出 NP 完全性)
最後,上一單元已證明 CIRCUIT-SAT 是 NP 完全的。閘構造再加上短子句補足,把它歸約到 3-SAT。由於 3-SAT 屬於 NP,它是 NP 完全的。同樣的公式也是普通的布爾公式,所以它們證明 SAT 是困難的,而 SAT 屬於 NP。另一種辦法是把任意布爾公式看作其語法樹電路,並用閘構造來編碼。兩條路線都不會把共享電路展開成可能巨大的樹。
例題詳解
例題 2.3.5
(編碼一個電路並恢復其內部值)
令 ,,輸出 。該公式包含三個 AND 子句、兩個 NOT 子句、三個 OR 子句和最後的單位子句 ,共九個子句。對輸入 ,唯一一致的閘值為 ,所以該公式在此輸入下可滿足。對 ,一致性迫使 ,與輸出單位子句矛盾。手工選取 無法繞過 OR 子句。
例題 2.3.6
(五文字子句有兩個連結變量)
對於 ,鏈為
若只有 為真,令 。第一個子句由 滿足,第二個由 滿足,最後一個由 滿足。若五個文字全為假,前兩個子句迫使兩個連結變量都為一,最後一個子句失敗。該構造使用三個子句,恰為 。
例題 2.3.7
(為甚麼不同的原子句需要不同的連結變量)
考慮 。固定 以及 ,使兩個原子句都為真。第一個四文字鏈迫使其連結變量為一,因為 為假。第二個迫使其連結變量為零,因為 為假。互不相同的新連結變量使兩個要求同時成立。若重用同一個連結變量,就會產生矛盾,並錯誤地拒絕這個滿足的原賦值。新變量是正確性的條件,而不只是命名上的偏好。
常見錯誤
反例模式
每個閘只用一個蘊涵是不夠的
如果 AND 閘 只用 表示,則 滿足該子句,儘管閘的輸出本應為零。隨後的輸出斷言就可能接受一個不可能的計算。必須使用完整的三子句模式;說「閘輸出蘊涵某個輸入為真」比 AND 關係弱。
常見錯誤
(等可滿足並不保持賦值的個數)
等可滿足也不同於保持滿足賦值的個數。閘的定義對每個原輸入有唯一一致的擴張,但長子句鏈可能有多個滿足的連結賦值。普通的 NP 困難性只需要保持存在性。計數歸約還需要額外的重數論證,不能僅僅因為判定歸約成立就加以斷言。
常見錯誤
(這個歸約並不求解公式)
這一變換並不求解目標公式。它構造一個規模受控的公式,其賦值在所述的存在意義上與原來對應。之後枚舉所有賦值仍可能需要指數時間;NP 完全性並不是多項式時間的可滿足性算法。
總結
新名字保持了電路的共享;局部子句強制每個閘的精確關係;連結鏈分配長子句,同時保持擴張的存在性。兩個方向與規模界使歸約完整。結合驗證者到電路的構造,這些論證在所指定的編碼下證明了 SAT 與 3-SAT 是 NP 完全的。
練習
快速檢查
(寫出 的子句,並驗證 的情形。)
解答 · 答案
子句為 、 和 。兩個輸入都為零時,前兩個已經為真,最後一個迫使 。因此輸入為假的情形並非不受約束。
快速檢查
(對八文字子句,鏈使用多少個新變量和多少個子句?)
解答 · 答案
有 個新變量和 個子句。它們的合取只有十八個文字出現,所以鏈的長度關於原子句長度是線性的。
快速檢查
(對四文字子句 ,給出對原變量的一個賦值,使其新連結變量的兩個取值都被容許。這對賦值計數說明了甚麼?)
解答 · 答案
令 ,。則無論 取何值, 與 都成立。因此一個原賦值有兩個擴張。該構造保持可滿足性,但不會自動保持其個數。
快速檢查
(說明如何處理含有空子句的 CNF 輸入,並解釋為甚麼把它映到空合取是錯誤的。)
解答 · 答案
空子句在每個賦值下都為假,所以整個 CNF 不可滿足,必須映到一個固定的不可滿足三 CNF。空合取為真;映到它會把否定實例變成肯定實例,破壞歸約的反向方向。
這完成了 Trevisan–Williams 講義中介紹的基於電路的路線。這裏給出的顯式子句模式與邊界約定,使保持可滿足性的各項陳述可以直接檢驗。