蘇 鑫，胡紅鋼

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

0 引言

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

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

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

證明LWE的方法是，對于BDDγ問題的一個輸入，格B，v∈n，設(shè)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的實例給出一個歸結(jié)辯駁的問題歸約到一組SAT實例上，從而構(gòu)造出一個具有平均復(fù)雜性的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。相反，輸入為子集和問題中無解的實例時，利用復(fù)雜性理論中的歸結(jié)辯駁可得到關(guān)于無解的證明。事實上，若coNP完全問題存在多項式規(guī)模的歸結(jié)辯駁時，則NP=coNP。之后，對兩種情況取異或運算，便得到兩種情況有且只有一種情況成立。這樣，可以把對于一個NP完全問題是否存在多項式時間算法對值為1的實例給出一個見證,并且對值為0的實例給出一個歸結(jié)辯駁，用一組合取范式表示。

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

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

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

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

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

1 預(yù)備知識

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

1.1類NP和類coNP

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

定義1(類NP)

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

(3)

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

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

定義2

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

(4)

定義3

(5)

定理1(Cook-Levin定理)

SAT問題是NP完全問題。

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

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

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

(6)

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

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

推論1

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

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

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

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

定義4(分布問題)

一個分布問題是一個序?qū)Α碙,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)對任意正整數(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′〉的多項式時間算法，則存在常數(shù)C,ε>0使得在任意M上均有

(7)

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

(8)

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

(9)

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

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

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

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

2 類P中的例子

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

(10)

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

(11)

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

對于二次方程ax2+bx+c=0，當判別式b2-4ac<0時，算法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)

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

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

當判別式|A|≠0時，算法A輸出t=1，與一個解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)

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

3 NP∪coNP與P

本節(jié)主要的內(nèi)容是給出一組合取范式，用來表示對于一個NP完全問題是否存在多項式時間算法A對值為1的實例給出一個見證并且對值為0的實例給出一個歸結(jié)辯駁。選取NP完全問題子集和問題。子集和問題的一個實例是(a1,a2,…,an,s)，簡記為(a,s)。當實例(a,s)無解時，算法A輸出t=0，并給出x·a=s的歸結(jié)辯駁c1,c2,…,cm。當實例(a,s)有解時，算法A輸出t=1與一個解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)

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

定理3

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

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

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

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

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

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

設(shè)p∈{0,1}*為NP完全問題的描述中的參數(shù)，如第3節(jié)中的p=(a,s)。設(shè)w(p)∈{0,1}*為NP完全問題的描述中的等式，如第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ù)的一個通式，進而轉(zhuǎn)化成相應(yīng)合取范式的通式。

4.2 基于其他的NP完全問題

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

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

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

…

…

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

…

…

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

ψ(p,Φp=1)

(17)

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

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

ψ′n=ψn∧τi。

(18)

5 結(jié)論

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