SAT子類的NP完全性和間隙問(wèn)題復(fù)雜性研究.pdf

1、從1972年發(fā)現(xiàn)NP-完全性以來(lái)，很多學(xué)者就對(duì)NP-難的優(yōu)化問(wèn)題能否有快速算法來(lái)計(jì)算其近似解感興趣，然而對(duì)大部分這類問(wèn)題，尋求有效的近似算法都令人失望。于是嘗試來(lái)證明求其近似解也是NP-難的，但除了極少個(gè)例成功之外就陷入停滯,并且發(fā)現(xiàn)傳統(tǒng)的Cook-Levin類型的歸約技術(shù)并不能用來(lái)證明這類問(wèn)題。直到1992年，由Arora等人發(fā)現(xiàn)了PCP定理，給出了NP類的一個(gè)新特性，并提供了關(guān)于歸約技術(shù)的一個(gè)新的起點(diǎn)，是極為令人震驚的。由PCP定理

2、出發(fā)，可以得出很多NP-難的優(yōu)化問(wèn)題，計(jì)算其近似解與計(jì)算其精確解具有同樣的難度，因而除非P=NP，否則不可能有多項(xiàng)式時(shí)間算法來(lái)求解?？梢哉f(shuō)，PCP理論是近20年來(lái)復(fù)雜性理論的重要成果之一，它是近似算法理論發(fā)展史上的一座里程碑。它對(duì)證明NP難優(yōu)化問(wèn)題的不可近似性起到了關(guān)鍵性的作用。
　　本文應(yīng)用PCP理論，對(duì)線性公式類LCNF及(k,s)-CNF公式類的NP完全性及其間隙問(wèn)題的復(fù)雜性進(jìn)行了研究。對(duì)(k,s)-ksCNF公式類的臨界函

3、數(shù)下界的估計(jì)進(jìn)行了探討，主要作了以下工作：
　　(1)考慮線性公式類LCNF，即公式中的任意兩個(gè)子句最多只有一個(gè)公共變?cè)SAT為L(zhǎng)CNF的滿足性判定問(wèn)題，用間隙歸約技術(shù)證明了MAX-LSAT屬于第二類不可近似問(wèn)題，即存在正數(shù)ε>0,MAX-LSAT要想取得近似比為1ε+的近似解是NP-難的。進(jìn)一步討論了LCNF公式類的子類：k-LCNF，即其公式的每個(gè)子句的長(zhǎng)度都是k，證明了對(duì)k≥3,MAX-k-LSAT≥也屬于第二類。

4、>　　(2)用極小不可滿足公式和遞歸方法解決了S.Porschen等人在[PS06b]提出的開(kāi)問(wèn)題：對(duì)于k≥5，LCNF≥k中是否含有不可滿足公式？這里L(fēng)CNF≥k表示每個(gè)子句長(zhǎng)度至少為k的線性公式構(gòu)成的類。S.Porschen用超圖和拉丁方的方法構(gòu)造出了LCNF≥3和LCNF≥4中的不可滿足公式，然而其方法過(guò)于復(fù)雜且不具有推廣性。我們給出了一種一般的構(gòu)造方法，即用遞歸的方法構(gòu)造出了k-LCNF中的不可滿足公式，因而證明了：對(duì)于k≥3，

5、k-LCNF含有不可滿足公式，得到了比Porschen中提出的問(wèn)題更強(qiáng)的結(jié)論。
　　(3)考慮(k,s)-CNF公式類，它是由每個(gè)子句長(zhǎng)度為k，而每個(gè)變?cè)霈F(xiàn)的次數(shù)不超過(guò)s的CNF公式構(gòu)成的類，而(k,s)-SAT為其滿足性判定問(wèn)題。證明了MAX-(3,4)-SAT屬于第二類不可近似的優(yōu)化問(wèn)題。并證明了：如果(k,s)-SAT是NP-完全的，則MAX-(k,s))-SAT也屬于第二類不可近似問(wèn)題。
　　(4)對(duì)(k,s)-S

6、AT中的臨界函數(shù)f(k)的界進(jìn)行了研究。Kratochvil證明了：對(duì)每個(gè)k≥3，存在正整數(shù)s=f(k)，使得所有(k,s)-CNF中的公式都是可滿足的；而(k,s+1)-CNF中存在不可滿足公式，從而(k,s+1)-SAT是NP完全的。關(guān)于f(k)，其精確值目前只知道f(3)=3,f(4)=，對(duì)k=5,6,…,9，目前已經(jīng)知道的最好結(jié)果由Hoory、Berman和Kratochvil等人得到如下：
　　5≤f(5)≤7,7≤f(

7、6)≤11,13≤f(7)≤17,24≤f(8)≤29,41≤f(9)≤51。
　　而對(duì)于k≥10，只有一般的估計(jì)式，相關(guān)的估計(jì)結(jié)果極少見(jiàn)到。我們通過(guò)用Berman等人構(gòu)造的函數(shù)（公式略）。
　　它滿足性質(zhì)：對(duì)正整數(shù)k,d，如果存在x∈(0,1)，使得g(k,d,x)>1，則(k,d)-CNF中的每個(gè)公式都是可滿足的。根據(jù)這個(gè)結(jié)果，結(jié)合函數(shù)作圖，通過(guò)二分法或變步長(zhǎng)搜索技術(shù)，對(duì)給定的正整數(shù)k，尋找存在x∈(0,1)，使函數(shù)g(

8、k,d,x)>1的最大正整數(shù)d，把這個(gè)最大值d作為(f,k)的下界估計(jì)值，從而給出了尋求f(k)下界的一種方法。利用此方法，我們得出了k=10,11,…,20時(shí)f(k)有如下下界：
　　f(10)≥75,f(11)≥136,f(12)≥251,f(13)≥463,f(14)≥860,f(15)≥1607,f(16)≥3013,f(17)≥5672,f(18)≥10715,f(19)≥20302,f(20)≥38574。