動機
子集和問題詢問:一列非負整數中,是否有若干個數恰好相加等於目標值。這個看似簡單的算術表述背後,隱藏著對子集的組合搜尋。為了證明其困難性,我們用被選中的數來編碼一個布爾賦值,並用各自獨立的數位列同時檢驗所有子句。
這個構造依賴於防止各列之間產生進位。每一列都有固定的目標值和很小的最大可能和,因此可以獨立地分析。我們以 3-SAT 的 NP 完全性作為背景知識;該定理在此作為起始結論引用,本節不予證明。
定義
定義 4.4.1
(子集和實例)
子集和問題的一個實例由一個有限的非負整數列表和一個非負目標值組成,所有數均以二進制編碼。若存在列表位置的某個子集,其對應的數之和等於目標值,則該實例是 yes 實例。不同位置上數值相等的數是不同的選擇。
定義 4.4.2
(3-CNF 公式的十進制列編碼)
3-CNF 公式具有明確列出的變量集合 和子句 ,每個子句恰好包含三個文字出現;容許重複出現。對每個變量構造兩個數,分別對應取真和取假。使用 個十進制數位:每個變量一列,每個子句一列。變量 的兩個數在其自身的變量列上數字為一,在其他變量列上為零。在子句列 中,取真選擇數的數字是 在 中出現的次數,取假選擇數的數字是 在 中出現的次數。
對每個子句列,再加入兩個鬆弛數,它們在該列的數字分別為一和二,其餘列均為零。目標值在每個變量列的數字為一,在每個子句列的數字為四。隨後,把這些十進制數轉換為二進制編碼,作為子集和問題的實例。
定理
定理 4.4.3
(歸約的正確性)
所構造的子集和實例有解,當且僅當輸入的 3-CNF 公式可滿足。
定理 4.4.4
(子集和問題的完全性)
假設 3-SAT 的標準 NP 完全性成立,則子集和問題在多項式時間多一歸約下是 NP 完全的。
證明思路或證明
證明
(各列的和都小於十,所以由數位決定相等)
即使任意選取全體數的一個子集,任何一列也不會產生十進制進位。變量列最多接收來自其兩個選擇數的二。一個子句有三個文字出現,因此在所有被選中的變量數中,它的貢獻至多為三;兩個鬆弛數至多再加三。其總和至多為六。因此,等式成立當且僅當每一列的和都等於目標的對應數字。
變量列的目標為一,所以其兩個選擇數中恰好選中一個。把這些選擇詮釋為一個真值賦值。在每個子句列中,被選中的變量數恰好貢獻為真的文字出現次數 。鬆弛數可以增加 或 ,所以目標四恰好在 時可以達到;當 時無法達到。因此,子集和問題的每個解都給出一個滿足賦值。
反過來,按某個滿足賦值的規定,選取取真或取假的選擇數。每個子句都有 個為真的出現。選取和為 的鬆弛數,而 屬於 。於是所有變量列和子句列都與目標吻合,所選的數之和等於目標值。重複的文字按出現次數計算,同樣的推理依然成立。
證明透視
無進位使各列互相獨立
「每一列的總和至多為六」這個界用了兩次。在正向推導中,它讓我們可以對任意子集逐位讀出目標整數,而不必事先知道選了哪些數;這正是每個變量列能強制恰好選一個的原因。在反向推導中,它保證由賦值構造的子集確實加起來等於目標。
不顯而易見的設計是鬆弛數 配上目標數字四:它們的子集和 恰好是真出現個數 所需的補數,而對 則不足。若改變進制或目標數字,就必須重新檢查這個分離性與無進位的界;沒有這個界,進位可能令表面上相符的數位掩蓋另一種選擇。
證明
(多項式規模與屬於 NP)
輸出包含 個數,每個數有 個十進制數位,所以它們的二進制長度和構造時間關於顯式公式的規模都是多項式的。一個子集就是長度為多項式的證書,而且二進制加法可在多項式時間內驗證其和。因此子集和問題屬於 NP;從 NP 完全的 3-SAT 出發的歸約證明了它是 NP 難的。空公式是可滿足的,並被映射到目標為零且沒有任何數的實例。格式錯誤的輸入編碼可以映射到一個固定的 no 實例,使歸約成為全映射。
例題詳解
例題 4.4.5
(一個含重複文字的子句)
對於 ,使用兩列:先是變量列,然後是子句列。取真數與取假數分別為 和 ;鬆弛數為 和 ;目標為 。選取真時得到 。選取假時,子句的貢獻為零,而兩個鬆弛數加起來只有三,因此無法達到目標。
例題 4.4.6
(一個有兩個為真出現的滿足子句)
若所選的變量數在某個子句列中貢獻 ,則選取數字為二的鬆弛數。這一列的和於是為四。鬆弛數的選取可以調整一個已滿足的子句,卻無法修補一個為真出現次數為零的子句。
例題 4.4.7
(一個有三個為真出現的子句)
若三個出現全為真,則變量的貢獻為三,數字為一的鬆弛數使其達到目標四。加上兩個鬆弛數後可能的最大貢獻為六,仍低於十進制的基數。
常見錯誤
反例模式
沒有鬆弛數的目標可能拒絕一個已滿足的子句
如果子句的目標為四,卻不提供任何鬆弛數,那麼恰有一個文字為真的子句只貢獻一,儘管它已被滿足,也無法通過數位檢驗。鬆弛數表示當 時所有可能的差值 。
常見錯誤
(沒有「各選一個」的約束就選數)
變量列的約束保證每個變量恰好選一個;只是選出一些看似為真的數並不足夠。兩個數都不選,該列為零而不是一;兩個都選,則該列為二。
常見錯誤
(只檢查由賦值構造的子集)
逆向的證明必須處理任意的子集和解,而不只是由賦值構造的子集,這需要對每個子集都成立的無進位界。子句列計算的也是文字出現的個數,包括重複的出現。
逐列構造這些數
數位只是概念上的標記;先排變量列、後排子句列的固定次序,給出一個普通的十進制整數。顯示時容許有前導零,但它們不改變其數值。一個子句的兩個鬆弛數在其他每一列上都為零,所以它們只影響該子句的總和。同一變量的兩個選擇在該變量列上相同,但根據各自使哪些文字為真而不同。
例如,若某個子句包含 的兩次正出現和另一個變量的一次出現,則 的取真選擇數在該子句列的數字為二,其取假選擇數在該處為零。若某個子句同時包含 和 ,則取真數與取假數分別記錄各自的出現。恰好選取 的一個數,就保證每個出現恰在其文字為真時貢獻一。
例題 4.4.8
(兩個子句與兩個變量)
設 ,。各列按 的次序書寫。 取真與取假的選擇數分別為 和 , 取真與取假的選擇數分別為 和 。目標為 。選取 時得到 ;在每個子句列上加上數字為二的鬆弛數,得 。若 為真而 為假,則所選的選擇數給出 ;第二個子句列為零,用至多為三的鬆弛數無法達到四。
只要每個數與目標使用同一次序,十進制列的次序就可以任意。把所構造的數轉換為二進制,改變的只是它們的表示,而不是數值,也不影響子集和的等式。明確列出變量,可保證 和 受公式表示長度所限制;未使用的已列出變量仍然得到一個選擇列。
為甚麼無進位論證適用於每個子集
逆向的蘊涵必須分析任意的子集和解,而不僅是由賦值構造出的子集。在我們知道每個變量恰好選取一個選擇數之前,兩個選擇數可能都被選中,也可能都未被選中。即便如此,一個變量列至多接收二。在子句列中,每個文字出現恰好出現在其變量的取真或取假選擇數之一中。因此選取所有選擇數,貢獻至多為該子句的三個出現。鬆弛數至多再加 ,所以每個子句的總和至多為六。
所有數位與數都是非負的。由於每一列的原始總和都小於十,普通十進制加法不會從任何一列產生進位。因此,一個和等於目標整數,當且僅當它的所有列總和都等於各自的目標數字。正是這一論斷,使變量列能夠強制一個選擇,使子句列能夠強制滿足性。若只對具有賦值形狀的子集給出和的界,逆命題的證明就會留下缺口。
概念視角代數
一條整數方程等於每列一條方程
由於沒有任何一列進位,這個實例等價於一個以 為未知數的線性方程組,每列一條方程。變量列 的方程為 。子句列 的方程為 ,其中 是被選中的選擇數裏 的出現次數之和, 表示是否選取兩個鬆弛數。十進制數字只是把所有這些方程打包成一條整數方程。
選取目標數字四,是為了把零個為真的出現與一個、兩個或三個為真的出現區分開。鬆弛數的和構成 。當 時,所需的補數分別為 。當 時,所需的補數為四,而它不可得。這些具體的數並非神聖不變,但換用不同的基數或目標,就需要重新檢驗這一區分與進位界。
歸約方向與證書
該映射以一個公式為輸入,產生一個子集和實例。因此,一個假想的多項式時間子集和判定器,只要先應用該映射,就能判定 3-SAT。這正是把 NP 難性從 3-SAT 轉移到子集和問題所需的方向。反方向的映射本身並不能證明子集和問題是困難的。
兩個解之間的變換是明確的。滿足賦值選取每個變量的一個數以及相應的鬆弛位置。和為目標的子集為每個變量恰好選取一個數;這些選擇確定一個滿足賦值。這是等可滿足性,並不保證在每一種可能的編碼約定下,公式的每個賦值恰好對應一個子集。例如,數值相等而列表位置不同的數,仍然是不同的子集選擇。
對於 NP 成員性,證書可以是一個指示所選列表位置的位向量。其長度為輸入整數的個數。驗證器把所選的二進制整數相加,並用多項式時間的整數算術把結果與二進制目標比較。數值本身可能很大,儘管它們的編碼很短;關於目標值的多項式時間界則是另一種偽多項式的論斷。
規模與邊界情形
每個所構造的十進制數至多有 位。由於它小於 ,其二進制長度至多是 的常數倍。共有 個數,每個數位都可以透過掃描明確列出的文字出現而算出。因此,該歸約在公式編碼的規模上以多項式時間運行,它並不枚舉所有賦值。
子句的空合取為真。當既沒有變量也沒有子句時,該構造產生空列表和目標零;空子集見證這是一個 yes 實例。當有變量而沒有子句時,每個變量列要求選取兩個選擇數之一,公式仍然可滿足。一個形式化的全映射還應規定對格式錯誤的編碼的行為。把每個格式錯誤的字串映射到一個固定的子集和 no 實例,是一種標準選擇,並不影響對合法公式的正確性證明。
這個構造是專門為恰好含三個出現的子句度身訂造的。若另一種輸入約定容許更短的子句,應先用重複出現來補足每個非空子句,或另做數位分析。空子句為假,可以直接映射到一個固定的 no 實例。這些選擇應當明確說明,而不應假設所有 3-SAT 約定都相同。
總結
變量列強制作出真值選擇,子句列統計為真的文字出現次數,鬆弛數位則恰好在每個子句被滿足時補滿目標。十進制的界防止了進位,使列的論證成為有效的整數和歸約。
練習
快速檢查
(一個子句列中兩個鬆弛數字的和可能是多少?)
考慮兩個鬆弛數的每個子集。
解答 · 答案
是 ,分別對應不選、只選一、只選二和兩個都選。
快速檢查
(為甚麼變量列不會向相鄰的列進位?)
數一數有多少個數在該列的數位非零。
解答 · 答案
最多只有兩個變量選擇數各貢獻一,所以該列的和至多為二,小於十。
快速檢查
(若一個子句有一個為真的出現,必須選取哪些鬆弛數字?)
子句列必須達到四。
解答 · 答案
兩個鬆弛數都要選,加上 ,與一個為真的出現合共達到四。
快速檢查
(為甚麼輸出長度是輸入長度的多項式?)
數一數數的個數和位數。
解答 · 答案
共有 個數,每個數有 個十進制數位;它們的二進制編碼總長度是多項式。