【正文】 18 [11]，極小不可滿足公式多項式公式的應(yīng)用，軟件學報， 2020， 17（ 5）： 12041212。（施普林格出版社，紐約 2020）。 作為一個例子，我們構(gòu)建了一個極小不可滿足的（ 3,4） CNF 計算公式 從以下的 MU(1)公式。所以，我們 有 _ ( ) _ ( ) 12 3max s at F max s at F m? ??和 1 ( )124( ) 1 var Fvar F? ??? 。 （ 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完整問題對于 3 SAT 的 NP完 整性 。 相反，我們認為 ? 是滿足 []xF 的正確指令 。 14 讓 我們 用 1[ , , ]mF C C? 作為 一個 3CNF 公式的例子 ，并 且用 ( , ) 1negF x ? 表示 每個變量 x 。 顯然，子公式 A 對于 nA 可滿足的， 并且 任何 指令 ? 滿足 A ， 1( ) ( )nxx???? 。 ( , )k b CNF?? ： CNF 公式的類，其中每一條款包含文字 屬于 k 并且 每個變量出現(xiàn) 的次數(shù)最多為 b。 ()varF 是 在公式 F 中出現(xiàn)的變量集。因此，該問題是（ 3,4） CNF是 NP完全問題 ， 并且 一些特性 圖 將有助于探討 NP難問題的復(fù)雜性。在公式和常規(guī)結(jié)構(gòu) 的類 中 ， 可能得到一些 可滿足性的特殊性質(zhì)和復(fù)雜的結(jié)果。 ( )clF 表示 公式 F 的 子句數(shù) ， ( )varF 表示公式 F 變量發(fā)生數(shù)。 CNF 公式的因子圖 和常規(guī)結(jié)構(gòu) 有 著 一些良好的性質(zhì)和 顯示 結(jié)果 的理論圖 ，可用于 研究它的 可滿足性和復(fù)雜性公式。 關(guān)鍵詞 ： 規(guī)則 ，極小不可滿足公式（ 3,4）， CNF 公式， 常規(guī) 結(jié)構(gòu)， NP 完全性 使 CNF 公式成為 命題公式的合取范式的類。所以，我們 用 MU（ k）其中 1k? 表示 極小不可滿足公式 。我們發(fā)現(xiàn)，極小不可滿足公式在減少一個給定的公式類 成為常規(guī)公式方面 具有重要應(yīng)用 [11]。一條子句 C 是一個析取文本， 1()mC L L? ? ? ，或者一組1{ , , }mLL文本。如果 ( , ) 0pos F x ?（或 ( , ) 0neg F x ? ），我們可以刪除所有包含 x? (或 x ）從原始公式的條文。 13 我們將使用下面的公式為減少轉(zhuǎn)換小工具公式。 注 2：該公式 G 可以作為一個小工具公式子句的長度長，或添加的發(fā)生 變化的 數(shù)量。我們引進了一套新的變量 [] ,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 出現(xiàn)四次， 其中 1 2( ), 0 9l s t k? ? ? ? ?。 16 10 ()() ( ) ( ) \ { }x v xv v v v ar F x?? ? ??? ? ? ?? 基于以上方法，我們構(gòu)建了一個公式 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}sat F C F C? ?? ? ?， ( ) | ( ) |sat F sat F??? 并且 _ ( )max sat F 表示 F 中 ( )sat F? 關(guān)于 ?的最大的變量 。下面 （ 3,4） CNF 公式具有規(guī)則結(jié)構(gòu)，其中的因子圖是一個普通的（ 3,4） 偶圖 ，變量節(jié)點度是四，第節(jié)點的度正是三。 [ 2], , B?ning，一 種 為 CNF 的極小不可滿足問題的一種有效算法，人工智能數(shù)學年刊， 1998,23（ 34）： 229245。 [ 9 ]美國 hoory 和美國 szeider，永無止境的 KCNF 公式與每個變量， 電子預(yù)印本系統(tǒng)，數(shù)學。 [14] 和巴拉克，計算復(fù)雜性的現(xiàn)代方法，劍橋大學出版社， 2020。 [ 7 ]，一個簡化的 NP完全可滿足性問題，離散數(shù)學應(yīng)用， 1984， 8（ 1） ： 8589。因此 有(15) (3, 4)MU CNF ??。 它是已知的最大 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 是不可近似性的 。我們有 ( ) 93var F m? ? 和 ( ) 124cl F m? ? 。 特別 的 ， ? 滿足 []xA 的 每個條款 ，但是不滿足 1( ) ( )stxx????? 。 （ 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 出現(xiàn)正四次 ，其中 1 , 0 9j s t k? ? ? ? ? 。 （ 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??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?。 公式 1[ , , ]mCC和 公式 1[ , , ]mCC???的 連接 ，有時寫為 11[ , , ] [ , , ]mmC C C C ???? 。 ( , ) ( , ) ( , )occ s F x po s F x neg F x??指變量出現(xiàn)次數(shù) 。因此，（ 3,4） 偶圖 的 一些結(jié)果和 性質(zhì) 可能 對研究 （ 3,4） CNF公式 有用 。在 [ 10 ]中 ，作者研究 發(fā)現(xiàn) 可滿足性和不可滿足 性 的公式的變量很少出現(xiàn) 在一起 。 如果 F 是永無止境的 并且 {}FC? 滿足任何 CF? ，那么公式 F 是 極小不可滿足公式（ MU）。因此 ,（ 3,4） SAT 是一個 規(guī)則 的 NP完全問題。 我們提出了一個從 3CNF 公式 轉(zhuǎn)化為 （ 3,4） CNF 公式極其規(guī)則結(jié)構(gòu)的多項式 ，其中每個子句包含三個字符，每個變量出現(xiàn)四次。 ( , )CNF nm 是CNF 公式和 變量 n 以及 子句 m 結(jié)合的 類。 提出了簡化的 NP完全可滿足性問題，其中發(fā)生在公式變量個數(shù)有 限 [ 7 ]。公式（ 3,4） CNF 的因子圖 具有規(guī)則的結(jié)構(gòu)，其中的變量節(jié)點的度是四， 子句 節(jié)點的度是三。 ( , )pos F x ( ( , )negFx ) 表示 F 中的變量的正（負） 出現(xiàn)的次數(shù)。 一個公式 1[ , , ]mF C C? 中的變量 n， 1,nxx屬于 ( , )CNF nm 可以表示為如下的矩陣， nm? ，,()ija 稱為 F 的 矩陣表示， ,ija ?? 如果 ijxC?? ， ,ija ?? 如果 ijxC? ，否則 , 0ija ? （或空白）。 注 1：該公式 cstA? 可以作為一個小工具的公式給定的變量替換所有 ()st? 出現(xiàn)依次減少的變量 1,stxx? 的數(shù)量。 （ 1 ） 引 入 了 一 組 新 的 變 量 [] 1{ , , }x stX x x ?? ，并定義一個公式[] 1 2 1 1[ ( ) , , ( ) , ( ) ]x s t s t s tA x x x x x x? ? ? ?? ? ? ? ? ? ? 它有一個對應(yīng)的隱含周期： 1 2 1 1s t s tx x x x x? ? ?? ? ? ? ?。這就要求 ? 必須滿足 [ ] [ ]xxAB? 的 每一條款。 F? 是 第三節(jié)的 （ 3,4） CNF 公式。 因此，如果能 同時 滿足多項式（ 3,4） CNF 公式和（ 3,4） CNF 多項式的大部分條款 1124? ，那么就是可 滿足 的 ， 如果能同時 滿足 （ 3， 4） CNF 公式和 （ 3， 4） CNF 多項式 的大部分條款 1? ，那么也是可 滿足 的 。 120123456789LLzzzzzzzzzz? ? ? ?? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ????????? 所得到的公式是一個包含 45 個變量和 60 條款 的 極小不可滿足公式。 [ 6 ]美國 Porschen， E. Speckenmeyer， ，線性 CNF 公式和可滿足性，離散應(yīng)用數(shù)學， 2020， 157（ 5）： 10461068。 [13] ，從 kCNF 到 tCNF 歸約的一種有效算法，南京大學學報數(shù)學半年刊， 2020， 22（ 1）： 5365。 CO／ 041167， 11 月 2020。 [ 3 ] , , ，極小不可滿足公式的固定條款變量差分多項式時間識別，計算機 科學理論 ， 20202 89（ 1）： 503516。因此，我們得到一個正規(guī)的 NP完全問題。 定義 ( )||()sat FFval F ?? ?和 _ ( )||() max sat FFval F ?。 定理 1 公式 F 是可滿足的當且僅當 1[ , , ]nppF 是滿足的。 引理 1 公式 F 是可滿足的當且僅當 []xF 是滿足的。 3.（