動機
判定算法只回答滿足賦值是否存在;學生往往還想得到賦值本身。對於 SAT,這兩個任務關係密切:詢問一個部分變量已固定的公式是否仍然可滿足,就能每次揭示見證的一位。只要見證長度受多項式界限制,同樣的想法對每個多項式時間可驗證的關係都適用。
把「是」與「否」兩種條件結合起來,會得到另一個有用的類。一個公式可以至少有一個滿足賦值,同時又不存在兩個不同的滿足賦值。第一個斷言有 NP 見證,第二個則是 coNP 斷言。清楚區分這兩種角色,可以避免把「恰有一個」誤當作普通的 NP 證書。
定義
定義 2.4.1
(多項式平衡的 NP 關係及其判定語言)
多項式平衡的 NP 關係是一個確定性多項式時間謂詞 ,並附帶一個固定的多項式 ,使得有效見證可以取為恰好 位。較短的表示可以透過長度標記加填充來編碼,驗證者負責檢查編碼並忽略填充部分。其判定語言為
搜尋過程必須對每個 輸出一個有效的 ;對於沒有見證的輸入,我們會明確說明它必須報告失敗,還是可以傳回任意字串。
定義 2.4.2
(前綴語言)
的前綴語言為
換言之,當部分見證 仍可補全為有效見證時,。
前綴語言屬於 NP:剩餘的後綴 是多項式長度的見證,驗證者檢查長度並計算 。過長的無效前綴一律拒絕。我們使用配套的 Cook–Levin 筆記中的結論:SAT 在多項式時間多一歸約下是 NP 完全的。
定理
定理 2.4.3
(由前綴判定進行搜尋)
對每個多項式平衡的 NP 關係,帶有 SAT 神諭的確定性多項式時間機器在見證存在時可以輸出一個有效見證,在見證不存在時報告失敗。在把前綴問題以多項式時間歸約為 SAT 之後,它至多使用 次神諭查詢。
該定理並不假設任意的判定語言 本身能夠回答每一個前綴問題。神諭解決的是前綴語言,並借助前綴語言到 SAT 的 NP 歸約。在把熟悉的 SAT 過程推廣到其他關係時,這一區別十分重要。
證明
證明
(逐位固定見證)
首先查詢 是否成立,其中 是空前綴。若不成立,則不存在見證,機器報告失敗。否則維持一個至少有一個有效補全的前綴 。若 ,查詢 是否成立。答案為是時,在 後附加 ;答案為否時,附加 。
該不變式得以保持。若存在以 開頭的有效補全,則第一個分支選中這樣的前綴。若沒有任何補全以 開頭,則舊前綴仍有某個有效補全,其下一位必為 。當長度達到 時,唯一可能的後綴為空,於是不變式表明 。機器先做一次初始查詢,之後每個見證位至多再做一次查詢。構造每個前綴查詢並把它歸約為 SAT 只需多項式時間。
輸出的是在序 下字典序最小的有效見證:在另一個有效見證與它首次不同的位置上,若存在以 開頭的有效補全,算法就不可能選擇 。字典序最小這一性質是不變式的有用推論,而不是額外的神諭假設。
證明透視
搜尋每一位背後的不變式
對 的查詢回答「否」之所以有用,只是因為當前前綴 已知存在補全。沒有這一不變式,在 0 分支失敗之後選擇 可能會走向另一個不可能的前綴。初始的存在性查詢建立了該不變式,之後的每次查詢都保持它。兩個分支的角色也不同:「是」不需要再檢查,因為它承諾的補全本來就延伸 ;「否」要通過不變式才轉化為關於 的資訊。最後,機器詢問的是 而不是 ,因為 的判定神諭不一定能回答關於部分固定見證的問題。
例題詳解
例題 2.4.4
(復原一個滿足賦值)
設 ,變量次序取 。初始查詢確認 可滿足。固定 後仍有滿足的補全,因此選擇 0。在該前綴之下,固定 是不可滿足的,因此選擇 1。輸出 滿足 ,並且是字典序最小的;另一個滿足賦值是 。
概念視角組合
把搜尋看成沿二叉樹向下走
把長度為 的字串排成二叉樹的葉,其中節點 的兩個子節點是 與 。當 ,即它下面的葉中有某個合法見證時,標記節點 。搜尋從根出發,根由最初的查詢檢驗;若 被標記便走向 ,否則走向 。它在最左的被標記葉結束,那就是字典序最小的合法見證。
例題 2.4.5
(一個非 SAT 的關係)
設 檢查位元串 是否編碼了圖 中恰好含 個頂點的獨立集,其中 包含在輸入裏,並約定了一種多項式長度的編碼。前綴問題問的是:一個部分編碼能否補全為這樣的集合。它屬於 NP,因為剩餘的位構成證書的其餘部分。SAT 神諭在多項式時間歸約之後可以判定每個前綴問題,所以同一搜尋過程在這樣的集合存在時就能構造出一個。它不需要枚舉所有頂點子集。
下面的例子說明,若不先建立不變式,會出現甚麼問題。
反例模式
跳過初始存在性查詢
斷言:對前綴 的回答為「否」之後,選擇位元 永遠正確。取 ,只有一個變量 。兩個取值都失敗:,。一個跳過初始存在性檢查的過程,測試 得到「否」後便自動輸出 ,而它並不滿足 。斷言不成立,因為空前綴本來就沒有補全。修正:先查詢 。這裏答案為「否」,機器報告失敗,這才是正確的。
的一個推論
定理 2.4.6
(判定與多項式見證搜尋)
若 ,則每個多項式平衡的 NP 關係都有確定性多項式時間的搜尋過程,且僅當不存在見證時才報告失敗。反之,若每個這樣的關係都有確定性多項式時間過程,能在見證存在時輸出有效見證(在否例上輸出可以是任意的),則 。
證明
(替換神諭;以見證搜尋判定 NP)
對於第一個方向,,所以假設給出了每個前綴問題的確定性多項式時間算法。把前一個證明中的神諭調用替換為該算法。調用次數為多項式個,因此完整的搜尋仍然是多項式時間。
對於逆向,任取語言 及其多項式平衡的驗證者 。運行假設的搜尋過程,然後檢查傳回字串的長度並計算 。當且僅當檢查通過時接受。在是例上,該過程給出有效見證;在否例上,無論該過程傳回甚麼,沒有任何字串能通過驗證者。由此得到的確定性多項式時間判定器表明 。由於 ,等式成立。
逆向需要的是一個統一的多項式時間搜尋過程,它在每個輸入(包括否例)上都停機。若某方法在沒有見證時可能永不停止,就得不到所述的多項式時間判定器。
NP 條件與 coNP 條件的結合
定義 2.4.7
(類 DP)
DP 中的語言要求某個 NP 條件成立,同時另一個(可能不同的)NP 條件不成立。
這裏的字母是複雜度類的名稱,並不表示動態規劃。對 NP 取 為空語言,對 coNP 取 為全集語言,即知 NP 與 coNP 都包含於 DP。僅憑這些包含關係,並不能說明任何一個包含是嚴格的。
定理 2.4.8
(SAT–UNSAT 是 DP 完全的)
由公式對 組成的語言(要求 可滿足而 不可滿足)在確定性多項式時間多一歸約下是 DP 完全的。
證明
(配對兩個 NP 歸約)
屬於 DP 可直接由定義得到:第一個分量屬於 SAT,第二個分量不屬於 SAT。關於困難性,設 ,其中 。利用 SAT 的完全性,在多項式時間內計算出公式 與 ,使得 當且僅當 可滿足,且 當且僅當 可滿足。單個映射 滿足
兩個歸約都是確定性的多項式時間歸約,所以它們的配對是一個有效的多一歸約。無效的編碼可以映射到固定的否例;這不會改變完全性。
例題 2.4.9
(兩個公式,兩種不同的角色)
取 與 。前者可滿足,後者不可滿足,所以 屬於 SAT–UNSAT。把它們交換後得到的是否例:新的第一個公式沒有見證。僅僅給出第一個公式的一個賦值,並不能證明第二個公式不可滿足。
恰有一個滿足賦值
定義 2.4.10
(EXACT-ONE-SAT)
EXACT-ONE-SAT 是由在固定的明確變量列表上恰有一個滿足賦值的公式組成的語言。
它屬於 DP。「至少一個」這一條件就是 SAT。「至少兩個」這一條件也屬於 NP:證書由兩個賦值組成,二者都滿足該公式,並且在所列變量上至少有一處不同。因此
兩個檢驗都可以透過 SAT 查詢實現:第二個檢驗使用變量的兩份副本、公式的兩份副本,以及一個多項式規模的約束,要求兩個賦值不同。因此 EXACT-ONE-SAT 也屬於 。
這是一個全語言:具有零個、一個或多於一個滿足賦值的公式,其是/否答案都有明確規定。而在「輸入保證至多有一個解」的承諾問題中,正確性的要求有所不同。我們不能由 EXACT-ONE-SAT 屬於 DP 就推出它是確定性 DP 完全的,也不聲稱已知它有多項式時間算法。
例題 2.4.11
(零個、一個和兩個賦值)
在只列出一個變量 的情形下,公式 有零個滿足賦值, 恰有一個, 有兩個。只有中間那個公式屬於 EXACT-ONE-SAT。其見證 證明了「至少一個」這一部分;而證明不存在第二個賦值,則是另一個獨立的 coNP 一側的任務。
常見錯誤
常見錯誤
(判定神諭不是前綴神諭)
針對原始是/否語言 的判定神諭,並不自動成為任意見證關係的前綴神諭。使一般搜尋證明成立的,是 的統一 NP 歸約。
常見錯誤
(一個滿足賦值不能證明唯一性)
單個有效賦值只證明 EXACT-ONE-SAT 中「至少一個」的一側,不能排除另一個不同的賦值;屬於 DP 本身也不能證明 DP 完全性。
常見錯誤
(可能在否例上循環的搜尋)
容許在否例上永不停機的搜尋方法,不是等價定理中所說的確定性多項式時間算法,也無法由它得到 的判定器。
總結
多項式長度的見證可以透過依次詢問各個前綴是否有補全而復原出來。若 P 等於 NP,這些前綴問題無需神諭即可判定;反之,統一的多項式時間見證搜尋會判定每一個 NP 語言。類 DP 則把一個 NP 條件與另一個 NP 條件的補的合取明確表達出來。
練習
快速檢查
(為甚麼 屬於 NP?)
說明證書是甚麼,以及驗證者檢查甚麼。
解答 · 答案
長度為 的後綴是多項式規模的證書。驗證者檢查前綴長度並計算 。
快速檢查
(當對前綴 的查詢失敗後,選擇位元 1 的依據是甚麼不變式?)
回想查詢之前對 已知甚麼。
解答 · 答案
當前前綴 已知存在某個有效補全。若沒有補全以 0 開頭,則至少有一個以 1 開頭。
快速檢查
(一般搜尋算法至多使用多少次 SAT 神諭查詢?)
把初始查詢與逐位查詢分開數。
解答 · 答案
至多 次:一次存在性查詢,加上每個見證位各一次查詢。
快速檢查
(對 ,求字典序最小的滿足賦值。)
按 的次序檢查賦值。
解答 · 答案
取 ,按 的次序檢查賦值; 不滿足,第一個滿足的賦值是 。
快速檢查
(在逆向的證明中,為甚麼否例上任意的輸出仍然會被正確拒絕?)
考慮否例上是否有任何字串是有效見證。
解答 · 答案
在否例上沒有任何字串是有效見證,所以確定性的長度檢查與驗證者檢查會拒絕搜尋過程輸出的任何內容。
快速檢查
(證明每個 NP 語言都屬於 DP。)
把 寫成一個語言與另一個語言的補的交集。
解答 · 答案
對 ,寫 ,而 。
快速檢查
(一個滿足賦值本身是否構成「公式恰有一個滿足賦值」的證書?)
考慮是否排除了第二個賦值。
解答 · 答案
不是。它證明至少存在一個賦值,但不能排除另一個不同的賦值。
快速檢查
(EXACT-ONE-SAT 屬於 DP,是否就證明它是 DP 完全的?)
回想完全性的兩個部分。
解答 · 答案
不是。完全性還需要在指定歸約下證明困難性,而這裏只確立了屬於 DP。另外,全語言 EXACT-ONE-SAT 對每個編碼的公式都規定了答案,而承諾問題的算法只需在滿足其承諾的輸入上正確。