動機
判定問題的歸約只需保持解是否存在;計數歸約則必須更為謹慎:引入輔助選擇可能令一個解變成多個解,從而改變答案。保計數(parsimonious)歸約則保持確切的計數。我們將構造一個由布爾(Boolean)電路到三文字子句的保計數歸約,並藉此觀察計數與一般可滿足性有何不同。接著我們研究積和式(permanent):它是對所有排列求和,所計算的正是二部圖中完美匹配的個數。
對於宣告了 個變量列表的布爾公式, 是使該公式為真的、對該列表的賦值個數。未被使用的已宣告變量仍然貢獻選擇數。在本單元中,3-CNF 公式的子句至多含三個文字;若要求每個子句恰好有三個文字出現,則可重複某個文字,把任何非空的較短子句補足,而不改變滿足賦值的集合。歸約所引入的變量會被計入輸出的變量列表,因此除非子句唯一地決定了它們,否則它們會對計數有所貢獻。
由計數函數 到 的保計數歸約,是一個多項式時間可計算的映射 ,使得對每個輸入都有 。這比僅僅保持函數值是否為零更強。其他計數歸約(包括神諭歸約)有不同的定義;完全性結果必須說明所採用的是哪一種。舉例說,加入一個不受約束的布爾變量的變換會把計數 變為 。把所返回的計數除以二可以還原 ,但這個原始映射並不是保計數的。當某個閘小工具對不同的輸入賦值產生不同數目的擴展時,這個區別就更為重要:此時單一固定的除數可能失效。
為何判定小工具可能改變計數
反例模式
輔助變量可以改變計數
假設有人聲稱,任何保持可滿足性的變換也保持滿足賦值的個數。取宣告變量列表為 的公式 ,它恰有一個滿足賦值。變量列表為 的公式 恰在 可滿足時可滿足,但它有兩個滿足賦值: 配 ,以及 配 。新增的變量不受約束。這個變換保持了解的存在性,但並非保計數;修補方法是要求每個輸入解恰有一個輸出擴展。
常見錯誤
(等可滿足並不意味著解的個數相等)
若證明了每個輸入解至少有一個輸出擴展,且每個輸出解都投影為某個輸入解,則所建立的只是可滿足性的等價。要保持確切的計數,還必須要求每個輸入解恰有一個輸出擴展,或存在其他明確的保計數雙射。僅僅引入輔助變量並檢查「是/否」方向,並不能確立這一性質。
編碼單個布爾閘
假設一個電路具有由 AND、OR、NOT 及常數閘構成的拓撲序,每個 AND/OR 閘有兩個輸入,每個 NOT 閘有一個輸入。為每個閘的輸出引入一個新變量。對於閘 ,施加
若 ,前兩個子句迫使 。若 ,第三個子句迫使 。因此這些子句恰在 時成立,而且一旦固定 ,容許的 是唯一的。
OR 與 NOT 閘可作同樣的分析。對 與 ,分別施加
對 OR 閘,第一、二個子句使 或 時 ,第三個子句使 時 成立;對 NOT 閘, 迫使 , 迫使 。在每種情形下,這些子句恰在 等於閘運算作用於其輸入的結果時成立,而且 由輸入唯一決定。常數一閘得到單元子句 ,常數零閘得到單元子句 ;在兩種情形下,其輸出都被唯一地迫定。閘可以共用前驅;每個閘仍然擁有各自的輸出變量。下面的計數論證會加入輸入賦值與輔助變量賦值之間的整體雙射。
例題 5.3.1
(雙向檢驗一個 AND 閘)
若 ,子句 迫使 ,而在 時三個子句皆成立。若 ,子句 迫使 ,這同樣滿足其餘子句。其餘兩個輸入對的情形類似。對每個固定的輸入對,恰有一個合法的 ,並且等於 。
定理 5.3.2
(由電路到 3-CNF 的保計數歸約)
存在一個多項式時間映射,把帶有已宣告輸入變量列表的布爾電路 映為 3-CNF 公式 ,使得 在其所有已宣告變量上的滿足賦值個數,等於 所接受的輸入賦值個數。
證明
(證明)
為每個閘建立一個新變量,並加入相應的閘等價子句。再加入一個單元子句,迫使輸出閘的變量為一。若輸出直接是某個輸入,則使用其單元子句。若輸出直接是常數,則加入一個新變量 ;對常數一迫使 ,對常數零則同時施加 與 。這兩種情形分別恰好保留每個輸入賦值一次,以及不保留任何輸入賦值。新變量與新子句的數目與電路描述的長度成線性關係。若採用此慣例要求,可重複某個文字把較短的非空子句補足為恰好三個文字;這不會引入新變量或新的滿足賦值。
固定對已宣告輸入變量的任一賦值。按拓撲序對電路求值,並為每個新變量賦予其閘的實際值。所有閘子句皆成立。反過來,在任何滿足賦值中,每個閘的子句迫使其新變量等於閘運算作用於前驅值的結果。沿拓撲序作歸納可知,每個閘變量都等於對 求值所得的值。因此固定的輸入賦值恰有一個滿足所有閘子句的擴展。輸出子句恰在 輸出一時接受該擴展。於是,向輸入變量的投影是由 的滿足賦值到 的接受輸入賦值的雙射,從而兩者計數相等。
證明透視
為何不僅需要擴展存在,還需要它唯一
這個歸約需要閘變量的兩項事實,它們的作用不同。擴展的存在性(按拓撲序對電路求值即得)說明每個被接受的輸入都會保留下來;唯一性(因為在前驅固定後,每個閘的子句迫使其變量取定值,沿拓撲序歸納即得)說明它恰好保留一次。可滿足性等價只需要存在性;保計數則兩者都需要。輸出閘上的單元子句隨後從輸入中恰好選出那些其唯一擴展的輸出為一的輸入。若沒有這個子句,每個輸入賦值仍恰有一個擴展,而公式在 個輸入變量上就有 個滿足賦值,與電路計算甚麼無關。
這個證明同樣處理了未被使用的輸入變量:其值在兩側的雙射中仍然是自由的輸入選擇。這種構造常被稱為閘編碼,但這裏關鍵的性質是輔助變量取值的唯一性,必須加以檢驗,而不能僅憑名稱推斷。
例題 5.3.3
(計算一個小的已編碼電路)
設 ,並引入一個閘變量 。加入三個 OR 等價子句及單元子句 。被接受的輸入賦值為 、 與 。對每一個,閘子句迫使 ;賦值 迫使 ,因而不滿足單元子句。所以輸出公式在 上恰有三個滿足賦值,而不是六個。
若從一個 見證驗證者出發,則以多項式大小的電路對多項式時間確定性計算作標準的一致模擬,可得到一個電路,其輸入位元是見證,而 則被硬接線。把該模擬與上述定理複合,便得到歸約至 的保計數歸約。這裏我們把機器到電路的模擬明確地視為未加證明的背景定理。閘編碼本身已在上面證明;不應把它誤當作該模擬的證明。
積和式與完美匹配
對於 矩陣 ,將其積和式定義為
這與行列式相似,但不對奇排列附加正負號。對於 – 矩陣,把第 行與第 列視為二部圖兩側的頂點,並且僅當 時才有邊 。
命題 5.3.4
(0–1 矩陣的積和式計算完美匹配個數)
對於 – 矩陣 , 等於其相伴二部圖中完美匹配的個數。把 映為此積和式的函數屬於 。
證明
(證明)
排列 為每一行恰好選出一列,並且每一列恰被使用一次。乘積 恰在所有被選取的配對都是邊時等於一;此時這些配對構成一個完美匹配。反過來,每個完美匹配在每一行中選出唯一的一列,因而對應唯一的排列。所有其他乘積皆為零,故該和式所計算的是匹配的個數。
為把這個計數表示為 見證函數,用固定寬度的二進位區塊編碼一個由 個列下標組成的建議序列。多項式時間驗證者會拒絕超出範圍或重複的下標,並檢查每條被建議的邊確實出現。每個完美匹配恰有一個這樣的有效序列,而無效的編碼則被拒絕。因此被接受的見證字串的個數就是積和式。 的情形可以每個下標使用一個位元,而有限個例外的大小可以明確地處理。
例題 5.3.5
(一個 積和式)
對於
考慮第一行所用的列。若它使用第 列,則餘下的 子矩陣全為一,貢獻兩個匹配。若它使用第 列,則第 行必須使用第 列,於是第 行使用第 列,貢獻一個匹配。第 列對第 行不可用。因此 。這個論證計算的是匹配而非帶符號的項;行列式的值可能不同。
奇偶性比精確計數更易提取
在域 上,。行列式的展開式為
把各項係數與整數行列式模二約化後,每個符號都等於一,故 。在 上做高斯(Gauss)消去法可在多項式時間內計算行列式。因此,我們可以判定二部圖的完美匹配個數是否為奇數,而無需用此方法算出該個數的確切值。
命題 5.3.6
(0–1 矩陣的積和式奇偶性)
對於 – 矩陣 , 的奇偶性可在確定性多項式時間內計算。
證明
(證明)
把 約化為 上的矩陣。逐項比較排列展開式,由於每個排列的符號皆為 ,行列式與積和式在該域中相等。基本行運算以多項式次數的域運算計算行列式;交換兩行會改變通常的符號,而這在 中同樣是 。所得結果就是模二約化後的積和式。它恰在整數計數為奇數時等於一。
例題 5.3.7
(即使存在匹配,奇偶性也可能為零)
對於全為一的 矩陣,每個排列各對應一個完美匹配,共有兩個。其積和式為 ,故奇偶性為零。其模二行列式也為零,因為它的兩行相等。因此偶數的奇偶性答案並不表示不存在匹配;它只說明確切的計數是偶數。
著名的結果指出,在適當的計數歸約下,– 積和式的精確計算是 完全的,這就是 Valiant 定理。它在此不予證明。多項式時間的奇偶性計算並不證明精確的積和式計算是容易的,而僅屬於 本身亦不能證明其困難性。同樣,Toda 定理需要超出本單元所述構造的額外神諭與歸約機制。
具有多項式時間遞推的計數問題
並非每個計數問題在同一意義下都是困難的。在有限有向無環圖中,由某個頂點到指定目標的有向路徑數目可以用動態規劃計算。令 ,代表由 到其自身的空路徑。按反向拓撲序處理其餘頂點,並令
從 出發的每條路徑恰好以一條出邊開始,因此各個求和項所計算的集合互不相交。沒有通往 的路徑的頂點得到零。源點處的值就是所求的計數。
例題 5.3.8
(不逐一列出而計算有向路徑)
設邊為 。從目標開始,得 與 。接著 ,,以及 。三條路徑為 、 與 。遞推式按首條邊把它們分組,並把每條路徑恰好計算一次。
對於有 個頂點的簡單無環圖,一條路徑至多經過每個頂點一次。頂點序列的個數有一個粗略上界 ,其位元長度僅為 ,所以遞推中所有的計數都具有多項式位元長度。因此多項式次數的加法便給出多項式時間的精確算法。無環性的假設對這個簡單遞推至關重要:有向圈可產生無窮多條遊走;即使只計算簡單路徑,遞推也必須記住哪些頂點已被使用。這個例子亦說明,僅僅屬於 並不能說明某個特定的計數是否困難。
練習與解答
快速檢查
(為甚麼加入一個不受約束的新布爾變量,一般會使滿足賦值的計數加倍?)
想想新變量可取多少個值。
解答 · 答案
每個原有的滿足賦值恰好以兩種方式擴展,即新變量等於零或一。沒有新的子句限制它。
快速檢查
(若 且 ,哪一個 的值滿足 AND 閘的等價子句?)
留意含 的子句。
解答 · 答案
子句 迫使 。在 時,三個 AND 等價子句皆成立。
快速檢查
(為甚麼電路到 CNF 的證明對每個輸入賦值恰好給出一個擴展?)
按拓撲序逐個閘考慮。
解答 · 答案
每個閘的子句把該閘的輸出強制為其已確定前驅的函數。沿拓撲序作歸納,便唯一地決定每個輔助變量。
快速檢查
(計算 的積和式。)
對 的兩個排列求和。
解答 · 答案
共有兩個排列,且各貢獻一,所以積和式為 。
快速檢查
(若 – 矩陣的積和式為奇數,其在 上的行列式是多少?)
比較兩個展開式模二的結果。
解答 · 答案
是一:行列式與積和式在模二下相等。
快速檢查
(在 上行列式為零,是否證明該二部圖沒有完美匹配?)
試試全為一的 矩陣。
解答 · 答案
不。它只證明匹配的個數為偶數。全為一的 矩陣有兩個匹配,而其在 上的行列式為零。