一個(gè)具有平均復(fù)雜性的SAT問(wèn)題

蘇 鑫，胡紅鋼

(中國(guó)科學(xué)技術(shù)大學(xué) 中國(guó)科學(xué)院電磁空間信息重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230026)

0 引言

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

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

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

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

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

=sTa+e'

(1)

將(a,〈v,y*〉)作為L(zhǎng)WE問(wèn)題的輸入，輸出得到向量s，則向量B·s即為BDDγ的一個(gè)解。

將對(duì)于一個(gè)NP完全問(wèn)題是否存在多項(xiàng)式時(shí)間算法對(duì)值為1的實(shí)例給出一個(gè)見(jiàn)證并且對(duì)值為0的實(shí)例給出一個(gè)歸結(jié)辯駁的問(wèn)題歸約到一組SAT實(shí)例上，從而構(gòu)造出一個(gè)具有平均復(fù)雜性的SAT問(wèn)題。

(1)本文方法。

考慮一個(gè)解決NP完全問(wèn)題的多項(xiàng)式時(shí)間算法，當(dāng)它的輸入為NP完全問(wèn)題中值為1的實(shí)例時(shí)，算法輸出為t=1，與該問(wèn)題的一個(gè)見(jiàn)證(witness)u；相反；當(dāng)輸入為NP完全問(wèn)題中值為0的實(shí)例時(shí)，算法輸出為t=0，與一段該問(wèn)題無(wú)解的證明。

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

(2)

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

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

(2)相關(guān)的工作。

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

表1 現(xiàn)有平均復(fù)雜性問(wèn)題的對(duì)比

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

1 預(yù)備知識(shí)

本節(jié)介紹相關(guān)的知識(shí)，包括類NP和類coNP的定義、平均復(fù)雜性理論及相應(yīng)的歸約，和永真式的歸結(jié)辯駁。

1.1類NP和類coNP

復(fù)雜性類是在特定計(jì)算能力上限內(nèi)能被計(jì)算的所有函數(shù)的集合。對(duì)布爾函數(shù)的計(jì)算定義了判定問(wèn)題或判定語(yǔ)言。類P包含了所有可以被高效求解的判定問(wèn)題，而類NP刻畫了可以被高效驗(yàn)證的所有問(wèn)題。

定義1(類NP)

語(yǔ)言L?{0,1}*屬于NP，如果存在多項(xiàng)式p(n)和一個(gè)多項(xiàng)式時(shí)間圖靈機(jī)M，使得對(duì)于任意x∈{0,1}*，有:

(3)

則稱u是關(guān)于語(yǔ)言L和圖靈機(jī)M的見(jiàn)證(witness)。

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

定義2

一個(gè)合取范式有如下的形式

(4)

定義3

(5)

定理1(Cook-Levin定理)

SAT問(wèn)題是NP完全問(wèn)題。

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

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

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

(6)

由于M是散漫圖靈機(jī)，函數(shù)F和這兩個(gè)下標(biāo)可以通過(guò)平凡輸入上模擬M來(lái)得到。函數(shù)F可以表示長(zhǎng)度為c2c的合取范式。因此可以構(gòu)造滿足性與L相同的合取范式，即L可以歸約到SAT。

以下是從SIS、LWE等平均復(fù)雜性問(wèn)題到平均復(fù)雜性的SAT問(wèn)題的轉(zhuǎn)換。

推論1

SIS、LWE等平均復(fù)雜性問(wèn)題可以轉(zhuǎn)化為具有平均復(fù)雜性的SAT問(wèn)題。

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

1.2 平均復(fù)雜性理論

如前文所說(shuō)，問(wèn)題對(duì)于不同的分布其復(fù)雜性也是不同的，因此有如下精確化的定義。

定義4(分布問(wèn)題)

一個(gè)分布問(wèn)題是一個(gè)序?qū)Α碙,D〉，其中L?{0,1}*是一個(gè)語(yǔ)言，而D={Dn}是一系列分布，Dn是{0,1}n上的一個(gè)分布。

下面定義分布問(wèn)題之間的歸約。

定義5(平均歸約)

稱分布問(wèn)題〈L,D〉平均歸約到問(wèn)題〈L′,D′〉，記為〈L,D〉≤p〈L′,D′〉，指存在多項(xiàng)式時(shí)間可計(jì)算的映射f和多項(xiàng)式p，q滿足：

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

(2)對(duì)任意正整數(shù)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。

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

(7)

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

(8)

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

(9)

1.3 永真式的歸結(jié)辯駁

命題邏輯是對(duì)兩千年來(lái)人們常用的推理模式的形式化描述。命題邏輯的主要任務(wù)是驗(yàn)證給定的布爾公式是否為永真式或矛盾式。

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

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

2 類P中的例子

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

(10)

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

(11)

同樣地，可以用合取范式表示乘法。根據(jù)SAT的完全性證明，一個(gè)多項(xiàng)式時(shí)間的圖靈機(jī)可以用多項(xiàng)式規(guī)模的合取范式表示。

對(duì)于二次方程ax2+bx+c=0，當(dāng)判別式b2-4ac<0時(shí)，算法A輸出t=0，并給出ax^2+bx+c=0的歸結(jié)辯駁：

(12)

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

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

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

(13)

進(jìn)而轉(zhuǎn)化成多項(xiàng)式規(guī)模的合取范式。

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

當(dāng)判別式|A|≠0時(shí)，算法A輸出t=1，與一個(gè)解x=A-1b，這里A-1為矩陣A的逆矩陣。

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

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

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

(14)

進(jìn)而轉(zhuǎn)化成多項(xiàng)式規(guī)模的合取范式。

3 NP∪coNP與P

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

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

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

(15)

進(jìn)而轉(zhuǎn)化成多項(xiàng)式規(guī)模的合取范式。

定理3

如果可以判定上述SAT問(wèn)題實(shí)例，則可以判斷對(duì)于一個(gè)NP完全問(wèn)題是否存在多項(xiàng)式時(shí)間算法對(duì)值為1的實(shí)例給出一個(gè)見(jiàn)證并且對(duì)值為0的實(shí)例給出一個(gè)歸結(jié)辯駁。

證明：因?yàn)閷?duì)于可滿足實(shí)例的函數(shù)f和對(duì)于不可滿足實(shí)例的歸結(jié)辯駁c1,c2,…,cm都是多項(xiàng)式長(zhǎng)度的，所以上述SAT問(wèn)題實(shí)例是多項(xiàng)式長(zhǎng)度的。

上述實(shí)例可滿足當(dāng)且僅當(dāng)對(duì)于子集和問(wèn)題，存在多項(xiàng)式時(shí)間算法A：當(dāng)實(shí)例(a,s)無(wú)解時(shí)，算法輸出t=0，并給出x·a=s的歸結(jié)辯駁c1,c2,…,cm；當(dāng)實(shí)例(a,s)有解時(shí)，算法輸出t=1與一個(gè)見(jiàn)證x=f(a,s)。又因?yàn)樽蛹蛦?wèn)題的NP完全性，所以如果可以判定上述SAT問(wèn)題實(shí)例，則可以判斷對(duì)于一個(gè)NP完全問(wèn)題是否存在多項(xiàng)式時(shí)間算法對(duì)值為1的實(shí)例給出一個(gè)見(jiàn)證并且對(duì)值為0的實(shí)例給出一個(gè)歸結(jié)辯駁。

4 第3節(jié)中合取范式的一些變形

本節(jié)給出上一節(jié)中構(gòu)造的合取范式的一個(gè)通式和一些變形問(wèn)題。

4.1 第3節(jié)中合取范式的通式

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

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

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

(16)

為第3節(jié)中函數(shù)的一個(gè)通式，進(jìn)而轉(zhuǎn)化成相應(yīng)合取范式的通式。

4.2 基于其他的NP完全問(wèn)題

通式的構(gòu)造只要求NP完全問(wèn)題的描述可以參數(shù)化。因此，將子集和問(wèn)題替換為其他NP完全問(wèn)題也可以構(gòu)造表示對(duì)于一個(gè)NP完全問(wèn)題是否存在多項(xiàng)式時(shí)間算法對(duì)值為1的實(shí)例給出一個(gè)見(jiàn)證并且對(duì)值為0的實(shí)例給出一個(gè)歸結(jié)辯駁的合取范式。

4.3 kSAT問(wèn)題的參數(shù)化與基于kSAT的構(gòu)造

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

…

…

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

…

…

將參數(shù)化的合取范式代入前面的通式中，可以得到基于SAT的構(gòu)造：

ψ(p,Φp=1)

(17)

其中ψ為4.1節(jié)中的通式。

4.4 隨機(jī)化的構(gòu)造

ψ′n=ψn∧τi。

(18)

5 結(jié)論

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