【導(dǎo)讀】NP-pleteness.,denoted. [2].So,wedenote()MUkasthe

　　

【正文】 [] 1 , 0 1 , 0 1[( ), , ( )]x stB y x y x?? ? ? ? ?和 []( 1, 2, , )xjT j s t??， []xjT 由下列 矩陣定義 ： ,0,1,2,3,4[],5,6,7,8,9jjjjjxjjjjjjyyyyyTyyyyy???????? ? ? ?? ? ? ?? ? ? ???? ? ? ??? ? ? ???? ? ? ?? ? ? ?? ? ? ????????? （ 3）定義了一個(gè)公式 []1 1 1 10 [ ] [ ] [ ] [ ]1[ ( ) , , ( ) , ( ) , , ( ) , ]x s s s s s t s t r e s tx x x xstF x f x f x f x f FA B T T ? ? ? ??? ? ? ? ? ? ?? ? ? ? ? 注意，子公式 [ ] [ ]xxAB? 包含 2( )st? 新條款的長度，子公式 [ ] [ ]1 xxstTT??? 包含 13( )st? 條款 ， 并且 新的變量 ,j jkxy 在 []0xF 出現(xiàn)正四次 ，其中 1 , 0 9j s t k? ? ? ? ? 。 （ 4）讓 1 2( ),stCC???作為 一個(gè)列表 在 [ ] [ ]xxAB? 的兩個(gè) 長度 條款，其中 ,1 ,2()l l lC L L??? 。我們引進(jìn)了一套新的變量 [] ,0 ,9{ , , }x lllZ z z? 和一 個(gè) 公式 []xlH ， 并且每一個(gè)長度 (1 2( ))lC l s t? ? ? ? 的屬于 lC? ， []xlH 用矩陣 表示為： ,1,2,0,1,2,3,4,5,6,7,8,9llllllllllllLLzzzzzzzzzz????? ? ? ?? ? ? ???? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ????????? 15 （ 5）定義一個(gè)公式 [] 1 1 1 1[ ] [ ] [ ] [ ]112 ( )[ ( ) , , ( ) , ( ) , , ( ) , ]x s s s s s t s t r e s tx x x xststF x f x f x f x f FH H T T? ? ? ???? ? ? ? ? ? ?? ? ? ? ? ? 注意，子公式 [ ] [ ] [ ] [ ]112 ( )x x x xststH H T T ??? ? ? ? ?包含 41( )st 條 長度為三的條款，每一個(gè)新的變量 ,lkz在 []xF 出現(xiàn)四次， 其中 1 2( ), 0 9l s t k? ? ? ? ?。 引理 1 公式 F 是可滿足的當(dāng)且僅當(dāng) []xF 是滿足的。 證明 ：讓 0? 是 一個(gè) 正確的指令 滿足 11[( ), , ( ), ( ), , ( ), ]s s s t re stF x f x f x f x f F??? ? ? ? ? ? ?，并且 0()xa? ? ，其中 {0,1}a? 定義一個(gè) 指令 []x? 如下： 0[][] [ ] [ ]12 ( )[ ] [ ]1( ) ( ) \ { }() 00xx stxxjjstxxllv v v ar F xa v Xv v Y Yv Z Z?? ??????????? ? ???????? 賦值滿足公式 []xF 。 相反，我們認(rèn)為 ? 是滿足 []xF 的正確指令 。對(duì)于 1 2( )l s t? ? ? ， 每個(gè) 指令 ? 滿足以下子公式： ,0,1,2,3,4,5,6,7,8,9llllllllllzzzzzzzzzz???????? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ????????? ? 是錯(cuò)誤的 指令對(duì)于 ,0lz ，因?yàn)楣?不能滿足下面的公式 ： ,1,2,3,4,5,6,7,8,9lllllllllzzzzzzzzz? ? ? ???? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ???? ? ? ?? ? ? ??????? 我們有 () 0v? ? 對(duì)于 ,0{ : 1, 2, , 2( )}lv z l s t? ? ?。這就要求 ? 必須滿足 [ ] [ ]xxAB? 的 每一條款。 特別 的 ， ? 滿足 []xA 的 每個(gè)條款 ，但是不滿足 1( ) ( )stxx????? 。因此，我們可以構(gòu)建一個(gè) 指令0?? 滿足 F 。 16 10 ()() ( ) ( ) \ { }x v xv v v v ar F x?? ? ??? ? ? ?? 基于以上方法，我們構(gòu)建了一個(gè)公式 1[ , , ]nppF ： 1 1 2 1 2 1 1 1[ ] [ , ] [ ] [ ] [ , , ] [ , , ] [ ], , , n n np p p p p p p p p pF F F F F ??? 我們 可以由引理 1 得到。 定理 1 公式 F 是可滿足的當(dāng)且僅當(dāng) 1[ , , ]nppF 是滿足的。 該公式 1[ , , ]nppF 具有以下特征： （ 1） 每個(gè)子句包含三個(gè)字符，每個(gè)變量出現(xiàn)在公式中 四次 。 （ 2) 1[ , , ] ( ) 31 | |nppvar F F??和 1[ , , ] ( ) ( ) 41 | |nppc l F c l F F? ? ? 其中1| | ( ( , ) ( , ) ) 3 ( )n iiiF pos F p ne g F p c l F?? ? ? ?? 最后，我們 發(fā)現(xiàn) （ 3,4） SAT 是 NP完整問題對(duì)于 3 SAT 的 NP完 整性 。 4. MAX (3,4)SAT 的不可近似性 假設(shè) 1[ , , ]mF C C? 是一個(gè) 3 CNF 公式 ， 公式變量 1,nxx。 F? 是 第三節(jié)的 （ 3,4） CNF 公式。我們有 ( ) 93var F m? ? 和 ( ) 124cl F m? ? 。 對(duì)于指令 ? 。定義 ( ) { : ( ) 1}sat F C F C? ?? ? ?， ( ) | ( ) |sat F sat F??? 并且 _ ( )max sat F 表示 F 中 ( )sat F? 關(guān)于 ?的最大的變量 。 定義 ( )||()sat FFval F ?? ?和 _ ( )||() max sat FFval F ?。 它是容易的，對(duì) 于 1( ) { , , }nvar F x x? 的 任何 指令 ? ，有 ?? 屬于 ()varF? ，如 ( ) ( ) 12 3sat F sat F m??? ? ??。所以，我們 有 _ ( ) _ ( ) 12 3max s at F max s at F m? ??和 1 ( )124( ) 1 var Fvar F? ??? 。這意味著，如果 F 的 一部分條款 ? 是 不滿足 的 ，那么一部分條款 124? 對(duì)于 F 是不可滿足的。 因此，如果能 同時(shí) 滿足多項(xiàng)式（ 3,4） CNF 公式和（ 3,4） CNF 多項(xiàng)式的大部分條款 1124? ，那么就是可 滿足 的 ， 如果能同時(shí) 滿足 （ 3， 4） CNF 公式和 （ 3， 4） CNF 多項(xiàng)式 的大部分條款 1? ，那么也是可 滿足 的 。 它是已知的最大 MAX 3SATIS 不可近似性 [ 14 ]， ,對(duì)于 任何 01??? ， 3SAT? 問題 是是 NP難的， 其中 3 { 3 : ( ) 1 }S AT F S AT v a l F? ?? ? ? ?并且 3 { 3 : }SA T F C N F F i s s at i s f i ab l e?? 因此，我們 MAX (3,4)SAT 是不可近似性的 。 基于極小不可滿足公式的應(yīng)用，我們已經(jīng)表明，可以減少 3SAT 問題的多項(xiàng)式（ 3,4）SAT。下面 （ 3,4） CNF 公式具有規(guī)則結(jié)構(gòu)，其中的因子圖是一個(gè)普通的（ 3,4） 偶圖 ，變量節(jié)點(diǎn)度是四，第節(jié)點(diǎn)的度正是三。因此，我們得到一個(gè)正規(guī)的 NP完全問題。未來的工作是探討（ 3,4） CNF 基于一些結(jié)果和公式（ 3,4） 偶圖 的性質(zhì) 。 作為一個(gè)例子，我們構(gòu)建了一個(gè)極小不可滿足的（ 3,4） CNF 計(jì)算公式 從以下的 MU(1)公式。 17 12345xxxxx? ? ? ?????? ? ? ?? ? ? ?? ? ? ???? ? ? ??? 每個(gè)子句 12()LL? 都在 1 2 1 2 4 5 4 5{ ( ), ( ), ( ), ( )}x x x x x x x x? ? ? ? ? ? ? ? ? ?中，我們將分別用下列公式的形式引入十個(gè)新變量 12()LL? 的條款。 120123456789LLzzzzzzzzzz? ? ? ?? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ????????? 所得到的公式是一個(gè)包含 45 個(gè)變量和 60 條款 的 極小不可滿足公式。因此 有(15) (3, 4)MU CNF ??。我們 對(duì) ( ) (3, 4)MU k CNF ??中不滿足 k 的 結(jié)果感興趣 . 參考文獻(xiàn) [ 1 ] 和 ，計(jì)算機(jī) 不可近似性 A 指南 和 NP完全性理論， 公司， 舊金山 ， 1979。 [ 2], , B?ning，一 種 為 CNF 的極小不可滿足問題的一種有效算法，人工智能數(shù)學(xué)年刊， 1998,23（ 34）： 229245。 [ 3 ] , , ，極小不可滿足公式的固定條款變量差分多項(xiàng)式時(shí)間識(shí)別，計(jì)算機(jī) 科學(xué)理論 ， 20202 89（ 1）： 503516。 [ 4 ] SPorschen, , and ,線性 CNF 公式， ，（主編），對(duì)可滿足性測試的理論與應(yīng)用第十九屆國 際會(huì)議（ sat2020），LNCS 4121， 2020，頁 212225。（施普林格出版社，紐約 2020）。 [ 5 ]美國 Porschen，和 ， NP 完全性的 SAT 約束線性公式的類別，廣州可滿足性邏輯會(huì)議建模， 111123 頁。 [ 6 ]美國 Porschen， E. Speckenmeyer， ，線性 CNF 公式和可滿足性，離散應(yīng)用數(shù)學(xué)， 2020， 157（ 5）： 10461068。 [ 7 ]，一個(gè)簡化的 NP完全可滿足性問題，離散數(shù)學(xué)應(yīng)用， 1984， 8（ 1） ： 8589。 [ 8 ]美國 Hoory 和美國 Szeider 永無止境的 KSAT 實(shí)例，計(jì)算每個(gè)變量， sat2020 會(huì)議， BC，溫哥華，加拿大。 [ 9 ]美國 hoory 和美國 szeider，永無止境的 KCNF 公式與每個(gè)變量， 電子預(yù)印本系統(tǒng)，數(shù)學(xué)。 CO／ 041167， 11 月 2020。 [ 10 ] 和 ，注意未完成重言式與有限數(shù)量的每個(gè)變量的出現(xiàn)，理論計(jì)算機(jī)科學(xué)， 2020， 238（ 12）： 495498。 18 [11]，極小不可滿足公式多項(xiàng)式公式的應(yīng)用，軟件學(xué)報(bào)， 2020， 17（ 5）： 12041212。 [12]， ，和張， kLACS（ 3k? ）是 NP 完全問題，軟件學(xué)報(bào)， 2020， 19（ 3）：511521。 [13] ，從 kCNF 到 tCNF 歸約的一種有效算法，南京大學(xué)學(xué)報(bào)數(shù)學(xué)半年刊， 2020， 22（ 1）： 5365。 [14] 和巴拉克，計(jì)算復(fù)雜性的現(xiàn)代方法，劍橋大學(xué)出版社， 2020。