【正文】 [14] 和巴拉克，計算復雜性的現代方法，劍橋大學出版社， 2020。 [12]， ，和張， kLACS（ 3k? ）是 NP 完全問題，軟件學報， 2020， 19（ 3）：511521。 [ 10 ] 和 ，注意未完成重言式與有限數量的每個變量的出現，理論計算機科學， 2020， 238（ 12）： 495498。 [ 9 ]美國 hoory 和美國 szeider，永無止境的 KCNF 公式與每個變量， 電子預印本系統(tǒng)，數學。 [ 7 ]，一個簡化的 NP完全可滿足性問題，離散數學應用， 1984， 8（ 1） ： 8589。 [ 5 ]美國 Porschen，和 ， NP 完全性的 SAT 約束線性公式的類別，廣州可滿足性邏輯會議建模， 111123 頁。 [ 4 ] SPorschen, , and ,線性 CNF 公式， ，（主編），對可滿足性測試的理論與應用第十九屆國 際會議（ sat2020），LNCS 4121， 2020，頁 212225。 [ 2], , B?ning，一 種 為 CNF 的極小不可滿足問題的一種有效算法，人工智能數學年刊， 1998,23（ 34）： 229245。因此 有(15) (3, 4)MU CNF ??。 17 12345xxxxx? ? ? ?????? ? ? ?? ? ? ?? ? ? ???? ? ? ??? 每個子句 12()LL? 都在 1 2 1 2 4 5 4 5{ ( ), ( ), ( ), ( )}x x x x x x x x? ? ? ? ? ? ? ? ? ?中，我們將分別用下列公式的形式引入十個新變量 12()LL? 的條款。未來的工作是探討（ 3,4） CNF 基于一些結果和公式（ 3,4） 偶圖 的性質 。下面 （ 3,4） CNF 公式具有規(guī)則結構，其中的因子圖是一個普通的（ 3,4） 偶圖 ，變量節(jié)點度是四，第節(jié)點的度正是三。 它是已知的最大 MAX 3SATIS 不可近似性 [ 14 ]， ,對于 任何 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 是不可近似性的 。這意味著，如果 F 的 一部分條款 ? 是 不滿足 的 ，那么一部分條款 124? 對于 F 是不可滿足的。 它是容易的，對 于 1( ) { , , }nvar F x x? 的 任何 指令 ? ，有 ?? 屬于 ()varF? ，如 ( ) ( ) 12 3sat F sat F m??? ? ??。定義 ( ) { : ( ) 1}sat F C F C? ?? ? ?， ( ) | ( ) |sat F sat F??? 并且 _ ( )max sat F 表示 F 中 ( )sat F? 關于 ?的最大的變量 。我們有 ( ) 93var F m? ? 和 ( ) 124cl F m? ? 。 4. MAX (3,4)SAT 的不可近似性 假設 1[ , , ]mF C C? 是一個 3 CNF 公式 ， 公式變量 1,nxx。 該公式 1[ , , ]nppF 具有以下特征： （ 1） 每個子句包含三個字符，每個變量出現在公式中 四次 。 16 10 ()() ( ) ( ) \ { }x v xv v v v ar F x?? ? ??? ? ? ?? 基于以上方法，我們構建了一個公式 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 得到。 特別 的 ， ? 滿足 []xA 的 每個條款 ，但是不滿足 1( ) ( )stxx????? 。對于 1 2( )l s t? ? ? ， 每個 指令 ? 滿足以下子公式： ,0,1,2,3,4,5,6,7,8,9llllllllllzzzzzzzzzz???????? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ????????? ? 是錯誤的 指令對于 ,0lz ，因為公式 不能滿足下面的公式 ： ,1,2,3,4,5,6,7,8,9lllllllllzzzzzzzzz? ? ? ???? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ???? ? ? ?? ? ? ??????? 我們有 () 0v? ? 對于 ,0{ : 1, 2, , 2( )}lv z l s t? ? ?。 證明 ：讓 0? 是 一個 正確的指令 滿足 11[( ), , ( ), ( ), , ( ), ]s s s t re stF x f x f x f x f F??? ? ? ? ? ? ?，并且 0()xa? ? ，其中 {0,1}a? 定義一個 指令 []x? 如下： 0[][] [ ] [ ]12 ( )[ ] [ ]1( ) ( ) \ { }() 00xx stxxjjstxxllv v v ar F xa v Xv v Y Yv Z Z?? ??????????? ? ???????? 賦值滿足公式 []xF 。我們引進了一套新的變量 [] ,0 ,9{ , , }x lllZ z z? 和一 個 公式 []xlH ， 并且每一個長度 (1 2( ))lC l s t? ? ? ? 的屬于 lC? ， []xlH 用矩陣 表示為： ,1,2,0,1,2,3,4,5,6,7,8,9llllllllllllLLzzzzzzzzzz????? ? ? ?? ? ? ???? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ????????? 15 （ 5）定義一個公式 [] 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 條 長度為三的條款，每一個新的變量 ,lkz在 []xF 出現四次， 其中 1 2( ), 0 9l s t k? ? ? ? ?。 （ 2 ） 引 入 新 的 變 量 集 [] ,0 ,9{ , , }x jjjY y y? 1, ,j s t??， 并 定 義 公 式[] 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）定義了一個公式 []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 出現正四次 ，其中 1 , 0 9j s t k? ? ? ? ? 。 對于一個固定的變量 x ，讓 11[ ( ) , , ( ) , ( ) , , ( ) , ]s s s t re stF x f x f x f x f F??? ? ? ? ? ? ?。因此，該問題（ 3,4） SAT 是 NP完全 問題 。 注 2：該公式 G 可以作為一個小工具公式子句的長度長，或添加的發(fā)生 變化的 數量。 （ 2 ） (4)MU 公式 1 1 1 2 2 2 3 3 3( , , , , , , , , , )G u x y z x y z x y z的定義是1 2 313( ) ( ( ) ( ) ( ) ( ) ) ( )j j j j j j j j j j jju u x y x y z x y z x y z z z z??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?。 公式 A 受 一種周期公式 1 2 1nx x x x? ? ? ?的影響：。顯然 1{( )}nA x x? ? ? 和1{( )}nA x x? ? ? ? ?兩者都是可滿足的， 11{ ( )} | ( ) n nA x x x x? ? ? ? ? ?和11{ ( ) } | ( ) n nA x x x x? ? ? ? ? ? ? ? ? ?。 13 我們將使用下面的公式為減少轉換小工具公式。 公式 1[ , , ]mCC和 公式 1[ , , ]mCC???的 連接 ，有時寫為 11[ , , ] [ , , ]mmC C C C ???? 。 ( , )k b CNF? ： CNF 公式的類，其中每一條款包含文字 屬于 k 并且 每個變量只出現 b 次。 我 們將使用下列符號： ( , )CNF n m? ： CNF 公式以及 變量 n 和子句 m 的公式的類。如果 ( , ) 0pos F x ?（或 ( , ) 0neg F x ? ），我們可以刪除所有包含 x? (或 x ）從原始公式的條文。 ( , ) ( , ) ( , )occ s F x po s F x neg F x??指變量出現次數 。 ( )clF 表示條款的數目， ( )varF （或 | ( )|var F ） 作為 F 中出現的變量的數目。 1()nF C C? ? ? ，或一組1{ , , }nCC條款或子句 1[ , , ]nCC的列表。一條子句 C 是一個析取文本， 1()mC L L? ? ? ，或者一組1{ , , }mLL文本。因此，（ 3,4） 偶圖 的 一些結果和 性質 可能 對研究 （ 3,4） CNF公式 有用 。 對于 一個 CNF 公 * 這項工作是由中國國家自然科學 基金項目（編號： 600863005） 12 式 1[ , , ]mF C C? ， 變量 1,nxx， F 的 因子圖是一個 偶 圖，表示 為 ( , , , )F var clG V V E ?? ，1{ , , }var nV x x? （ 稱 為 可 變 節(jié) 點 集 ）， 1{ , , }cl mV C C? （ 稱 為 第 節(jié) 點 集 ），{ ( , ) : }i j i jE x C x oc c urs in C? 和標簽函數 : { 1, 1}E? ? ? ? 由 ( , ) 1ijxC? ?? ， 其中 ijxC? ， ( , ) 1ijxC? ??并且 ijxC?? 定義 。 在本文中，我們提出了一個由 3CNF 公式轉化為 （ 3,4） CNF 公式 的規(guī)則 ，其中每個子句包