一個具有平均復雜性的SAT問題

蘇 鑫，胡紅鋼

(中國科學技術大學 中國科學院電磁空間信息重點實驗室，安徽 合肥 230026)

0 引言

在計算復雜性理論中，很多問題都是研究在所有輸入上求解的復雜性，亦即最壞復雜性。NP完全性是研究最壞復雜性的經典范例。但在考慮復雜性時，分析者通常只對“實踐中”出現的問題實例感興趣，這就需要考慮平均復雜性。人們已經發現，很多基于圖論的NP完全問題在“平均圖”上很容易求解。如3-COLOR以很高概率可以在線性時間求解。Bollobas對這一領域進行了綜述[1]。

為了建立平均復雜性理論，人們定義了分布NP(distNP)類。LEVIN L A證明了distNP完全問題的存在性[2]，但他構造的問題并不是自然的。LIVNE N給出了一個很強的結果，他證明了所有自然的NP完全問題都有平均復雜性的形式[3]。事實上，他利用了NP完全問題的一些性質，構造了問題的合理分布，使其成為distNP完全問題，但不足之處是分布是不自然的。

證明SIS的方法是，對于SIVPγ問題的一個輸入，格B∈n×n，以連續高斯分布N(0,s2)選取n維向量x1,…,xm，令yi=ximodP(B)，設ai=「q·B-1yi」，以此得到m=O(n2)個向量a1,…,am。若SIS(a1,…,am,q)返回一個短向量e，||e||≤β，則向量是SIVPγ的一個解。

證明LWE的方法是，對于BDDγ問題的一個輸入，格B，v∈n，設v=Bs+e，其中Bs是要找的近向量，||e||≤γλ1(B)。以離散高斯分布DB*,r隨機選取向量y*，這里，格B*為格B的對偶格。則y*=B*·a。

〈v,y*〉=sTBTB*a+e'

=sTa+e'

(1)

將(a,〈v,y*〉)作為LWE問題的輸入，輸出得到向量s，則向量B·s即為BDDγ的一個解。

將對于一個NP完全問題是否存在多項式時間算法對值為1的實例給出一個見證并且對值為0的實例給出一個歸結辯駁的問題歸約到一組SAT實例上，從而構造出一個具有平均復雜性的SAT問題。

(1)本文方法。

考慮一個解決NP完全問題的多項式時間算法，當它的輸入為NP完全問題中值為1的實例時，算法輸出為t=1，與該問題的一個見證(witness)u；相反；當輸入為NP完全問題中值為0的實例時，算法輸出為t=0，與一段該問題無解的證明。

xi=f(a1,a2,…,an,s)

(2)

其中i=1,2,…,n。將這n個等式代入輸入的實例中可得到x·a=s。相反，輸入為子集和問題中無解的實例時，利用復雜性理論中的歸結辯駁可得到關于無解的證明。事實上，若coNP完全問題存在多項式規模的歸結辯駁時，則NP=coNP。之后，對兩種情況取異或運算，便得到兩種情況有且只有一種情況成立。這樣，可以把對于一個NP完全問題是否存在多項式時間算法對值為1的實例給出一個見證,并且對值為0的實例給出一個歸結辯駁，用一組合取范式表示。

注意到，在此方法中，只需要選取的NP完全問題的描述可以用參數表示出來。很多NP完全問題，如頂點覆蓋(Vector Cover)、極大團(Maximal Clique)問題，它們的問題描述可以用圖的鄰接矩陣An×n表示。因此，這些問題也可以用來構造具有平均復雜性的SAT實例。最后，給出一種將SAT問題描述參數化的方法，使得SAT問題本身也可以用來構造具有平均復雜性的SAT實例。

(2)相關的工作。

一方面，有許多工作研究求解隨機SAT的算法上，以找到易于求解的SAT問題上[16-18]。另一方面，有很多關于平均復雜性問題的構造。評價一個平均復雜性問題的好壞可以用三個參數衡量：首先，是問題的自然性；其次，是問題所服從分布的簡單性；第三，是歸約的初始問題的最壞復雜性。將現有結果從這三個角度進行了總結和對比，見表1。SIS、LWE問題和基于圖論雖然是不同的組合問題，但通過適當的轉換都可以轉換成SAT問題(推論1)。因此，也將它們列入表中進行對比，如表1所示。

表1 現有平均復雜性問題的對比

從表1可看出，目前現有的結果有這樣的規律：對于基于NP完全問題的構造幾乎分布都是復雜的，而對于分布簡單的問題它的復雜性幾乎都是弱于NP完全問題的。因此，構造出分布簡單且復雜性高的平均復雜性問題，對理論和密碼學應用都具有很重要的意義。據我們所知，關于SAT平均復雜性的形式只有文獻[3]提出過。事實上，通過利用Cook-Levin定理的證明方法，可以將文獻[4～15]和文獻[17]、[18]中的結果轉化為多項式規模的SAT問題(推論1)。因此，也可以將這些結果歸入到平均復雜性的SAT問題中。本文亦針對SAT問題，給出一個構造清晰，但基于一個弱于判定NP∪coNP是否等于P的問題，該問題以現有的方法是無法判定的。基于此，提出下面的公開問題，即是否可以構造基于判定NP∪coNP是否等于P的具有平均復雜性的問題。

1 預備知識

本節介紹相關的知識，包括類NP和類coNP的定義、平均復雜性理論及相應的歸約，和永真式的歸結辯駁。

1.1類NP和類coNP

復雜性類是在特定計算能力上限內能被計算的所有函數的集合。對布爾函數的計算定義了判定問題或判定語言。類P包含了所有可以被高效求解的判定問題，而類NP刻畫了可以被高效驗證的所有問題。

定義1(類NP)

語言L?{0,1}*屬于NP，如果存在多項式p(n)和一個多項式時間圖靈機M，使得對于任意x∈{0,1}*，有:

(3)

則稱u是關于語言L和圖靈機M的見證(witness)。

設φ是變量u1,…,un上的一個布爾函數且z∈{0,1}n，則φ(z)表示將φ的變量依次賦予z中各個值之后φ的取值。如果存在賦值z使φ(z)等于1，則稱φ是可滿足的，否則稱φ是不可滿足的。如果變量u1,…,un上的布爾函數是在變量或變量的取反上OR操作所得的若干個函數上的AND操作，則稱該函數是合取范式(Conjunctive Normal Form，CNF)。

定義2

一個合取范式有如下的形式

(4)

定義3

(5)

定理1(Cook-Levin定理)

SAT問題是NP完全問題。

證明：SAT問題顯然屬于NP，因此，僅需證明它是NP難的。設L是一個NP語言，故存在多項式時間圖靈機M使得對于任意x∈{0,1}*，x∈L??u∈{0,1}p(|x|),M(x,u)=1。不失一般性，可假設圖靈機M只有兩條帶，一條輸入帶和一條工作/輸出帶；M是散漫圖靈機，即帶頭移動不依賴帶上內容。

設M所有的狀態集合為Q，字母表為Γ。M運行到第i步的快照為三元組〈a,b,q〉∈Γ×Γ×Q，其中a、b為帶頭在兩條帶上讀到的符號，q為此時M所處的狀態。第i步的快照記為zi。為了驗證zi的正確性，只需查看zi-1,ypos(i),zprev(i)，其中pos(i)表示M在第i步時帶頭在輸入帶的位置；prev(i)是M的帶頭在工作帶上在第i步之前最后與第i步在工作帶上的位置相同的那個步驟(若第i步的位置是首次訪問的，則prev(i)=1)。故存在函數F:{0,1}2c+1→{0,1}c使得：

zi=F(zi-1,ypos(i),zprev(i))

(6)

由于M是散漫圖靈機，函數F和這兩個下標可以通過平凡輸入上模擬M來得到。函數F可以表示長度為c2c的合取范式。因此可以構造滿足性與L相同的合取范式，即L可以歸約到SAT。

以下是從SIS、LWE等平均復雜性問題到平均復雜性的SAT問題的轉換。

推論1

SIS、LWE等平均復雜性問題可以轉化為具有平均復雜性的SAT問題。

證明：設M是求解或判定SIS(LWE)問題的多項式時間圖靈機。利用定理1中的證明方法，則圖靈機M的快照zi=〈a,b,q〉∈Γ×Γ×Q可以用函數式(6)驗證，這樣可以得到相應的合取范式。由于從SIS(LWE)的實例到相應合取范式的映射是一一對應的，故所得到的也是具有平均復雜性的SAT問題。

1.2 平均復雜性理論

如前文所說，問題對于不同的分布其復雜性也是不同的，因此有如下精確化的定義。

定義4(分布問題)

一個分布問題是一個序對〈L,D〉，其中L?{0,1}*是一個語言，而D={Dn}是一系列分布，Dn是{0,1}n上的一個分布。

下面定義分布問題之間的歸約。

定義5(平均歸約)

稱分布問題〈L,D〉平均歸約到問題〈L′,D′〉，記為〈L,D〉≤p〈L′,D′〉，指存在多項式時間可計算的映射f和多項式p，q滿足：

(1)對任意x∈{0,1}*，|f(x)|=p(|x|)且x∈L?f(x)∈L′；

(2)對任意正整數n和y∈{0,1}p(n)，Pr[y=f(Dn)]≤q(n)·Pr[y=f(D′p(n))]。

定理2

如果〈L,D〉≤p〈L′,D′〉且〈L′,D′〉∈distP中，則〈L,D〉∈distP。

證明:假設A′是求解〈L′,D′〉的多項式時間算法，則存在常數C,ε>0使得在任意M上均有

(7)

設f是〈L,D〉到〈L′,D′〉的歸約映射，則有判定L的算法A：在輸入x上，先計算f(x)，然后輸出A′(f(x))。只需證明算法A在服從分布D的所有輸入上的平均復雜度是多項式時間。不失一般性，假設在任意x上，|f(x)|=|x|^d。為了完成定理的證明,只需證明

(8)

其中q(n)是分布支配性條件中出現的多項式。根據A的定義和本文的假設條件可知：

(9)

1.3 永真式的歸結辯駁

命題邏輯是對兩千年來人們常用的推理模式的形式化描述。命題邏輯的主要任務是驗證給定的布爾公式是否為永真式或矛盾式。

本文給出歸結(resolution)的定義，它可以用來證明給定的公式是矛盾式。令φ是一個n元合取范式，φ的子句分別是c1,c2,…,cm。對于j>m，歸結過程將在之前得到的子句c1,…,cj-1上利用如下規則導出子句cj：假設存在變量xi和子句C、D使得xi∨C和xi∨D都是之前導出的子句，則令cj=C∨D。重復上述過程，直到得到關于某個變量xi上的兩個矛盾子句xi和xi，歸結過程結束。φ的歸結辯駁(resolutionrefutation)是指存在上述矛盾的子句序列c1,…,cT，其中c1,…,cm是φ的子句，而cj,j>m，是在c1,…,cj-1上導出的子句。顯然，導出的子句都蘊含在之前得出的子句中，故歸結是一個可靠的證明系統。如果φ是永真式，則φ存在一個有限長度的歸結辯駁，故歸結也是完備的。若每個不可滿足的布爾公式都存在多項式長度的歸結辯駁，則NP=coNP。

證明歸結下界的方法目前有瓶頸法與插值方法等。

2 類P中的例子

先從類P中的問題入手，之后再對NP完全問題進行討論。選擇二次方程和線性方程組求解問題，熟知這兩個問題有多項式時間求解算法，亦即在類P中。本節先從這兩個問題入手，說明多項式時間求解算法的存在性可以用一組多項式規模的合取范式表示。事實上，設變量a,b,c1,c2∈{0,1}，則等式a=b可以用合取范式

(10)

表示。加法a+b=(c1c2)2，其中(c1c2)2為二進制表示，可以表示為合取范式

(11)

同樣地，可以用合取范式表示乘法。根據SAT的完全性證明，一個多項式時間的圖靈機可以用多項式規模的合取范式表示。

對于二次方程ax2+bx+c=0，當判別式b2-4ac<0時，算法A輸出t=0，并給出ax^2+bx+c=0的歸結辯駁：

(12)

因此，算法A的存在性可以用函數表示為：

?c1,c2,…,cm,f:[(t=0)∧(c1,c2,…,cm為ax2+bx+c=0的歸結辯駁)

⊕[(t=1)∧(x=f(a,b,c))∧(ax2+bx+c=0)]

(13)

進而轉化成多項式規模的合取范式。

對于一個線性方程組Ax=b，其中A為n×n的矩陣，x和b為n維向量。為了簡化問題的描述，假設(A,b)的秩為n。當行列式|A|=0時，算法A輸出t=0，并給出Ax=b的歸結辯駁：如果原線性方程組有解，則矩陣A和(A,b)應有相同的秩。

當判別式|A|≠0時，算法A輸出t=1，與一個解x=A-1b，這里A-1為矩陣A的逆矩陣。

因此，算法A的存在性可以用函數表示為：

?c1,c2,…,cm,f:[(t=0)∧(c1,c2,…,cm為Ax=b的歸結辯駁)]

⊕[(t=1)∧(x=f(A,b)∧Ax=b)]

(14)

進而轉化成多項式規模的合取范式。

3 NP∪coNP與P

本節主要的內容是給出一組合取范式，用來表示對于一個NP完全問題是否存在多項式時間算法A對值為1的實例給出一個見證并且對值為0的實例給出一個歸結辯駁。選取NP完全問題子集和問題。子集和問題的一個實例是(a1,a2,…,an,s)，簡記為(a,s)。當實例(a,s)無解時，算法A輸出t=0，并給出x·a=s的歸結辯駁c1,c2,…,cm。當實例(a,s)有解時，算法A輸出t=1與一個解x=f(a,s)。因此，算法A的存在性可以用函數表示為：

?c1,c2,…,cm,f:[(t=0)∧(c1,c2,…,cm為x·a=s的歸結辯駁)]

⊕[(t=1)∧(x=f(a,s)∧x∈{0,1}n∧x·a=s)]

(15)

進而轉化成多項式規模的合取范式。

定理3

如果可以判定上述SAT問題實例，則可以判斷對于一個NP完全問題是否存在多項式時間算法對值為1的實例給出一個見證并且對值為0的實例給出一個歸結辯駁。

證明：因為對于可滿足實例的函數f和對于不可滿足實例的歸結辯駁c1,c2,…,cm都是多項式長度的，所以上述SAT問題實例是多項式長度的。

上述實例可滿足當且僅當對于子集和問題，存在多項式時間算法A：當實例(a,s)無解時，算法輸出t=0，并給出x·a=s的歸結辯駁c1,c2,…,cm；當實例(a,s)有解時，算法輸出t=1與一個見證x=f(a,s)。又因為子集和問題的NP完全性，所以如果可以判定上述SAT問題實例，則可以判斷對于一個NP完全問題是否存在多項式時間算法對值為1的實例給出一個見證并且對值為0的實例給出一個歸結辯駁。

4 第3節中合取范式的一些變形

本節給出上一節中構造的合取范式的一個通式和一些變形問題。

4.1 第3節中合取范式的通式

設p∈{0,1}*為NP完全問題的描述中的參數，如第3節中的p=(a,s)。設w(p)∈{0,1}*為NP完全問題的描述中的等式，如第3節中的w(p)為x·a=s。則函數

ψ(w,p)=?c1,c2,…,cm,f:[(t=0)∧(c1,c2,…,cm為w(p)的歸結辯駁)]

⊕[(t=1)∧(x=f(p))∧w(p)]

(16)

為第3節中函數的一個通式，進而轉化成相應合取范式的通式。

4.2 基于其他的NP完全問題

通式的構造只要求NP完全問題的描述可以參數化。因此，將子集和問題替換為其他NP完全問題也可以構造表示對于一個NP完全問題是否存在多項式時間算法對值為1的實例給出一個見證并且對值為0的實例給出一個歸結辯駁的合取范式。

4.3 kSAT問題的參數化與基于kSAT的構造

這里給出將kSAT問題的實例參數化的方法，這樣，可以基于kSAT問題構造合取范式。方法是，列出k-合取范式中可能出現的子句，即所有包含不多于k個文字的子句。之后引入系數pi，i=1,2,…,q(n)。具體地，kCNF中所有可能出現的子句如下：

…

…

對于每個子句，引入系數pj∈{0,1}，j=1,2,…,q(n)，這里q(n)為所有子句的個數，q(n)=O(nk)。將pj與相應子句作“或”運算。參數化的合取范式是這些新的子句作“與”運算，記為Φp。它的構造如下：

…

…

將參數化的合取范式代入前面的通式中，可以得到基于SAT的構造：

ψ(p,Φp=1)

(17)

其中ψ為4.1節中的通式。

4.4 隨機化的構造

ψ′n=ψn∧τi。

(18)

5 結論

本文給出一個可以歸約到判定對于一個NP完全問題是否存在多項式時間算法，對值為1的實例給出一個見證，并且對值為0的實例給出一個歸結辯駁歸約到一組SAT實例上，從而構造出一個具有平均復雜性的SAT問題。首先給出問題在類P上的類比，之后利用子集和問題給出了構造和證明。同時給出了構造合取范式的通式，使得可以參數化的NP完全問題可以代入通式得到新的合取范式，也給出將SAT問題參數化的方法，從而代入到通式，最后給出了隨機化的構造。