• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2019-09-13 02:58:48胡紅鋼
      關(guān)鍵詞:通式子句復(fù)雜性

      蘇 鑫,胡紅鋼

      (中國(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)造。

      猜你喜歡
      通式子句復(fù)雜性
      命題邏輯中一類擴(kuò)展子句消去方法
      “絕對(duì)差數(shù)列”的性質(zhì)
      PFNA與DHS治療股骨近端復(fù)雜性骨折的效果對(duì)比
      命題邏輯可滿足性問(wèn)題求解器的新型預(yù)處理子句消去方法
      簡(jiǎn)單性與復(fù)雜性的統(tǒng)一
      科學(xué)(2020年1期)2020-08-24 08:07:56
      探討一類遞推數(shù)列不動(dòng)項(xiàng)的計(jì)算通式
      西夏語(yǔ)的副詞子句
      西夏學(xué)(2018年2期)2018-05-15 11:24:42
      應(yīng)充分考慮醫(yī)院管理的復(fù)雜性
      自然數(shù)方冪和的一個(gè)計(jì)算通式
      運(yùn)用萬(wàn)有引力定律處理衛(wèi)星問(wèn)題的通式及例析
      沂水县| 临沂市| 康定县| 贺兰县| 永靖县| 宝清县| 桦川县| 延津县| 台北县| 长海县| 西宁市| 区。| 玉山县| 泽州县| 本溪市| 天峨县| 塔城市| 林州市| 德阳市| 资兴市| 宝兴县| 潢川县| 大冶市| 商丘市| 莱芜市| 加查县| 永靖县| 隆回县| 汤阴县| 丁青县| 五莲县| 奈曼旗| 布尔津县| 丰县| 类乌齐县| 天长市| 昭平县| 黄陵县| 富裕县| 赤壁市| 浑源县|