判定問題問的是見證是否存在;計數問題問的是見證有多少個。另一種觀點上的轉變,是把「對每個輸入長度皆適用的單一算法」換成一族布爾(Boolean)電路,每個長度各有一個電路。這兩種對基本模型的延伸,揭示了不同的困難來源。計數衡量解空間的大小,因此其輸出所含的資訊多於僅記錄解空間是否非空的那一個位元。相對地,非一致電路放寬了「單一有限描述須處理所有輸入長度」的要求,而這種放寬改變了「高效」的含義,其方式在一致圖靈(Turing)機模型中並無對應。本單元仔細發展這兩個想法,準確說明用到哪些假設,並區分哪些在此證明、哪些只是引用為背景。
為何要計數,為何要用電路?
考慮一條由排程或配置問題產生的布爾公式。一個回答「是否存在有效排程?」的求解器,只提供一個位元的資訊。在應用中,人們往往想知道更多:有效排程共有多少個、所有賦值中有效者佔多大比例,或隨機賦值成功的概率有多大。這些都是計數問題。它們在數學上同樣自然,因為非確定型機器的接受路徑數目是輸入的一個良定義函數,而該函數可以用研究語言時所用的同一套基於歸約的方法來研究。
電路處理的是另一個問題。圖靈機是一個必須對任何長度的輸入都能運作的單一有限對象。電路則只是針對某一長度的有限對象。若我們問計算 位元上的某函數需要多少個閘,便得到一個無需涉及任何機器即可研究的組合度量。代價是,電路序列不必由任何規則生成。準確理解放棄該規則所得所失,是本單元的第二個主題。
這兩個主題相遇於一個共同點。在兩種情形中,語言 的判定問題都被一個更豐富的對象取代:第一種情形是由字串到數的函數,第二種情形是由有限對象構成的序列。在兩種情形中,與熟悉的類 作比較時,都須謹慎說明究竟量度的是甚麼。
計數見證
定義 5.1.1
(類 #P)
函數 屬於 ,若存在一部非確定型多項式時間圖靈機,使得 等於該機器在輸入 上的接受計算路徑數目。等價地,給定一個多項式時間驗證者及固定的多項式見證長度,它計算的是接受見證的數目。固定長度的約定確保每個見證恰好對應一條路徑。
兩種描述的等價性取決於一個記帳上的要點。在驗證者的表述中,存在一個多項式時間謂詞 及一個多項式 ,使得
由於每個見證的長度都恰為 ,不同的見證即是不同的二進位字串,而猜測 再運行 的非確定型機器,每個見證恰有一條路徑。若見證長度可變,則一個字串可能是另一個字串的前綴,見證與路徑之間的對應就需要另行論證。另請注意 ,故 的值只有多項式個位元;這就是精確計數函數被寫成具有多項式個輸出位元的原因。
對於帶有指定變量列表的布爾公式 , 計算該列表上的滿足賦值數目。列表是重要的:加入一個未使用的變量會使計數加倍,儘管可滿足性不變。判定問題 SAT 只問計數是否為正。因此,多項式時間的精確計數算法可以判定 SAT,但此觀察並不能確立相反方向的蘊涵。
這種關係可以表述為精確的單向比較。若 可在多項式時間內計算,則對於帶有變量列表 的輸入 ,我們計算 ,並恰在其非零時接受,這便判定了 SAT。此論證無法反向進行:一個僅報告是否存在滿足賦值的神諭,並不明顯地揭示有多少個。以下的計數恆等式則闡明見證的數目如何組合。
一個例子
例題 5.1.2
(計算賦值數目)
對於 ,在指定變量 上,兩個子句合起來迫使 ,而 任意。因此 。在變量列表 上,同一表達式的計數為 ,因為未使用的 的任一取值都擴展每個滿足賦值。
此例背後的規律是一般性的。若 在 個變量的列表上有 個滿足賦值,而我們附加 個不出現於 的變量,則每個滿足賦值有 種擴展方式,故新的計數為 。反之,在 個變量上計數為 的公式,在所有賦值中的密度為 ,而附加未使用的變量並不改變此密度。因此,密度是在變量列表的選擇下保持不變的量,而原始計數則不是。
另外兩個計數計算
例題 5.1.3
(計算帶奇偶約束的公式)
設 ,變量列表為 ,其中 為互斥或。第一個合取項恰在 時成立,第二個恰在 時成立。自由選取 ,則 與 被迫確定。因此恰有兩個滿足賦值,即 與 ,故 。逐一枚舉全部 個賦值可驗證此結果:賦值 、、、、、 各自違反兩個條件之一,只剩下所列的兩個。密度為 。
例題 5.1.4
(以分情況與補集計數)
設 ,變量列表為 。滿足賦值必須使三個變量中至少兩個為真,因為若至多一個變量為真,則不含該變量的那個子句(或當無變量為真時的任一子句)會不成立。反之,若至少兩個變量為真,則每一對變量中都有一個為真,故三個子句皆成立。計算至少兩個變量為真的賦值:恰兩個為真有 個賦值,三個全為真有 個。因此 。以補集交叉驗證:使公式不成立的賦值是至多一個變量為真者:,且 ,與所需一致。
這些計算之所以容易,只因公式很小且結構性很強。對於具有數百個變量的一般 CNF 公式,目前並無已知的一般多項式時間精確計數方法,這正是 令人感興趣的部分原因。
變量互不相交公式的計數
以下恆等式描述當公式使用互不相交的變量時,計數如何組合。
命題 5.1.5
(變量互不相交公式的合取與析取之計數)
設 為變量列表 上的布爾公式, 為列表 上的布爾公式,其中 與 沒有共同變量。下面右邊的計數各自使用其本身的列表 與 。則在合併列表 上,
此外,在相同假設下,。
證明
(證明)
合併列表上的一個賦值是一個序對 ,其中 賦值給 , 賦值給 。由於 只涉及 ,它在 處的真值只取決於 ;同樣, 的真值只取決於 。設 且 ,則在各自的列表上 且 。
對於合取, 恰在 且 時滿足 ,故滿足集是笛卡兒積(Cartesian product) ,它有 個元素。
對於析取, 恰在 或 時滿足 。滿足 的序對集是 ,大小為 。滿足 的序對集是 ,大小為 。它們的交集是 ,大小為 。容斥原理給出 。
證明透視
變量互不相交在哪裏用到
整個證明依賴一個歸約:序對 滿足 恰當 ,滿足 恰當 。這是因為 不含 中的變量, 不含 中的變量;這也是唯一用到該假設的地方。有了這一點,合取的滿足集就是乘積集 ,析取的滿足集則是兩個柱集 與 的聯集。聯集的大小並不等於兩個柱集大小之和,因為它們恰好在 上重疊;容斥原理把這個重疊部分扣除一次。若 與 共用某個變量,「」與「」就不再是對不同座標的條件,滿足集也就不是乘積集,合取的計數便無法從兩個單獨的計數直接讀出。
作為數值檢驗,取 (故 ,計數為 )及 (故 ,計數為 )。析取公式給出 。直接計算,三個變量上的 僅在 且 時為假,這是 個賦值,故其為真者有 個。兩種計算結果一致。
此命題顯示,對於變量互不相交的公式,計數可以分解為乘積,而判定問題只看每個因子是否非零。它也提醒我們,析取並不具可加性:析取的計數取決於兩邊各自的變量個數,這是對變量列表依賴性的另一例證。
電路與非一致觀點
布爾電路是由閘構成的有限有向無環圖,其輸入節點帶有位元或常數;其大小為閘的數目。電路族 判定一個語言,是指對每個 及每個 位元字串, 都給出其正確的成員位元。類 由具有多項式大小電路族的語言組成。該族不必能由 計算出來:這就是非一致的特徵。 中的每個語言都有多項式大小的電路,其方法是展開一個多項式時間的計算;我們不加證明地使用該模擬定理。
具體地說, 意指存在一個多項式 及電路 ,使得 至多有 個閘,且對每個 , 當且僅當 。量詞結構是「存在一個序列」,而不是「存在一個產生序列的算法」。這是與一致定義之間唯一的差別,而下一個結果顯示這個差別是實質性的。
命題 5.1.6
(非一致性可以編碼不可判定的資訊)
存在一個屬於 的不可判定一元語言。
證明
(證明)
的子集有不可數多個,而圖靈機只有可數多個,故可選取一個不可判定的一元語言 。對每個長度 ,令 先檢查其 個輸入位元是否全為 ,然後輸出硬接線的位元,該位元指示 是否成立。此電路有 個閘。其硬接線位元的選取不必能由 計算,而該族在所有二進位字串上判定 。因此,單憑多項式電路大小並不蘊涵可判定性。
此構造值得仔細審視。當 時,「所有輸入皆為 」的檢驗是 個輸入的合取,需要 個二元 AND 閘。硬接線位元 然後要麼(若 )再以一個 AND 閘結合,要麼(若 )以常數 輸出取代。對 ,總數至多為 個閘;當 時,使用適當的常數輸出。此電路族的大小當然是多項式的。不可判定性僅透過序列 進入,而沒有任何算法能產生該序列。
反例與精確假設的作用
三個小觀察說明了為何前述陳述中的假設不能隨意捨棄。
第一,沒有變量互不相交的條件,分解式不成立。
反例模式
共用變量時分解式不成立
假設有人聲稱對所有公式都有 。取 及 ,在單變量列表 上。則 (只有 ),(只有 ),乘積為 。但 沒有任何滿足賦值,其計數為 。修補方法就是命題的假設: 與 必須使用互不相交的變量列表,這樣滿足的序對才是「獨立地選一個滿足 的 與一個滿足 的 」。
共享的變量把各因子耦合在一起,因此不能假定這兩個選擇是互相獨立的。
第二,計數取決於所宣告的變量列表。公式 在列表 上計數為 ,但在列表 上計數為 。任何省略列表的關於 的陳述都是含糊的。
第三,沒有一致性的多項式電路大小本身並不保證存在算法,硬接線的一元語言便是明證。相對地,一致族是指:多項式時間機器在輸入 上輸出 的描述。對這樣的族,該語言屬於 ,因為只需構造 並對其求值。這就是由多項式時間一致族到 的包含關係。其逆,即透過展開多項式時間機器來構造多項式時間一致族,是一個標準的模擬結果,在此不加證明地使用。
此處引用而未證明的內容
矩陣的積和式,以及計算它是 完全的這一定理,是核心的更多例子;Valiant 定理在此不予證明。本單元也不證明 Toda 定理或 Karp–Lipton 定理。這些結果需要精確的歸約、神諭約定及額外的機制,才能負責任地使用。未經證明的依賴包括:為驗證者等價性而對非確定型機器所作的正規化,以及以一致多項式大小電路對多項式時間計算的模擬;其餘一切,包括乘積性命題及不可判定性的例子,均已從定義出發加以證明。
常見錯誤
(電路並非自動就是一致算法)
對每個電路大小的多項式界,並不提供從 構造該電路的多項式時間程序。一致性是額外的要求。硬接線的一元語言例子使這一區別具體化。
常見錯誤
(讀取計數而不看其變量列表)
引述「 的滿足賦值數目」而不指明變量列表是不完整的,因為每個未使用的變量都會使計數加倍。比較兩個公式的計數,只有在共同的列表上才有意義,或在除以 取得密度之後才有意義。
練習與解答
快速檢查
( 在變量列表 上有多少個滿足賦值?)
數一數不滿足的賦值。
解答 · 答案
三個:除了 之外的所有賦值都滿足該公式。
快速檢查
(為何多項式大小的電路族不一定能由圖靈機判定一個語言?)
想想定義對從 到 的映射有何要求。
解答 · 答案
定義對從 到 的映射沒有任何可計算性要求。該族可以硬接線一個不可判定的位元序列,如一元語言的例子所示。
快速檢查
(利用乘積性命題,計算 在列表 上的 。)
先檢查兩個合取項是否使用互不相交的變量。
解答 · 答案
公式 (變量 )與 (變量 )的變量互不相交。 的計數為 , 的計數為 ,故乘積為 。直接計算: 被迫確定,且 ,給出 個賦值。
快速檢查
(一個公式在 個變量的列表上有 個滿足賦值。附加 個未使用的變量之後,其計數與密度各是多少?)
每個滿足賦值有 種擴展方式。
解答 · 答案
新的計數在 個變量上為 。之前的密度為 ,之後為 ,保持不變。
快速檢查
(證明若 ,則其補集也屬於 。)
把每個電路稍作修改。
解答 · 答案
給定 的電路 ,其大小至多為 ,在 的輸出之後加上一個 NOT 閘而得 。它至多有 個閘,仍是多項式的,且對長度為 的 , 恰在 時成立。注意此處不需要也沒有用到一致性。