蘇 鑫,胡紅鋼
(中國(guó)科學(xué)技術(shù)大學(xué) 中國(guó)科學(xué)院電磁空間信息重點(diǎn)實(shí)驗(yàn)室,安徽 合肥 230026)
在計(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)題。
本節(jié)介紹相關(guān)的知識(shí),包括類NP和類coNP的定義、平均復(fù)雜性理論及相應(yīng)的歸約,和永真式的歸結(jié)辯駁。
復(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)題。
如前文所說(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)
命題邏輯是對(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é)下界的方法目前有瓶頸法與插值方法等。
先從類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ī)模的合取范式。
本節(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é)辯駁。
本節(jié)給出上一節(jié)中構(gòu)造的合取范式的一個(gè)通式和一些變形問(wèn)題。
設(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)合取范式的通式。
通式的構(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é)辯駁的合取范式。
這里給出將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é)中的通式。
ψ′n=ψn∧τi。
(18)
本文給出一個(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)造。