【文章內(nèi)容簡介】 e that? is a truth assignment satisfying []xF . For each1 2( )l s t? ? ? , the assignment? satisfies following subformulas: ,0,1,2,3,4,5,6,7,8,9llllllllllzzzzzzzzzz???????? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ????????? The assignment ? force ,0lz to be false, because the following formula is an unsatisfiable formula: ,1,2,3,4,5,6,7,8,9lllllllllzzzzzzzzz? ? ? ???? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ???? ? ? ?? ? ? ??????? We have that () 0v? ? for ,0{ : 1, 2, , 2( )}lv z l s t? ? ?. It requires that? must satisfy each clause in [ ] [ ]xxAB? . Specially, ? satisfies each clause in []xA , it forces that 1( ) ( )stxx????? . Therefore, we can construct an assignment 0?? satisfyingF . 10 ()() ( ) ( ) \ { }x v xv v v v ar F x?? ? ??? ? ? ?? ■ Based on the above method, we construct a formula 1[ , , ]nppF step by step: 1 1 2 1 2 1 1 1[ ] [ , ] [ ] [ ] [ , , ] [ , , ] [ ], , , n n np p p p p p p p p pF F F F F ???. By lemma 1, we have that Theorem 1 The formulaF is satisfiable if and only if 1[ , , ]nppF is satisfiable. The formula 1[ , , ]nppF has the following characterizations: (1) Each clause contains exactly three literals, and each variable appears exactly four times in the formula. (2) 1[ , , ] ( ) 31 | |nppvar F F?? and 1[ , , ] ( ) ( ) 41 | |nppc l F c l F F? ? ?, where1| | ( ( , ) ( , ) ) 3 ( )n iiiF pos F p ne g F p c l F?? ? ? ??. Finally, we have that the problem (3,4)SAT is NPplete by the NPpleteness of 3 SAT . 8 4 Inapproximability of MAX (3,4)SAT Let 1[ , , ]mF C C? be a 3CNF formula with variables 1,nxx. F? is the (3,4)CNF formula 1[ , , ]nxxF in section 3. We have ( ) 93varF m? ? and ( ) 124cl F m? ? . For an assignment ? , denote ( ) { : ( ) 1}sat F C F C? ?? ? ?, ( ) | ( ) |sat F sat F??? ,and _ ( )max sat F is maximum of ( )sat F? for all? assignments of variables inF . We define ( )||()sat FFval F ?? ?and _ ( )||() max sat FFval F ?. It is easy to get that for any assignment ? over 1( ) { , , }nvar F x x? , there is an assignment ?? over ()varF? , such that ( ) ( ) 1 2 3sa t F sa t F m??? ? ??. So, we have that _ ( ) _ ( ) 12 3m ax sat F m ax sat F m? ??and 1 ( )124( ) 1 var Fvar F? ???. It is implies that if a ? fraction of the clauses ofF is not satisfiable, then a124?fraction of the clauses ofF? is not satisfiable. Hence, if one could distinguish in polynomial time between satisfiable (3,4)CNF formulas and (3,4)CNF formulas in which at most a (1124?)fraction of the clauses can be satisfied simultaneously, then one could distinguish in polynomial time between satisfiable 3CNF formulas and 3CNF formulas in which at most a (1? )fraction of the clauses can be satisfied simultaneously. It is known that MAX 3SATIS inapproximable [14], ., for any 01??? , the decision problem 3 SAT? is NPhard, where 3 { 3 : ( ) 1 }S AT F S AT v a l F? ?? ? ? ?and3 { 3 : }SA T F CN F F i s sat i sf i abl e?? . Therefore, we have that MAX (3,4)SAT is inapproximable. 5 Conclusions and future works Based on the application of minimal unsatisfiable formulas, we have show that 3SAT can be reduce polynomial to (3,4)SAT. Following a (3,4)CNF formula has a regular structure, which the factor graph is a regular (3,4)bigraph that the degree of variable node is exactly four, the degree of clause node is exactly three. So, we get a regular NPplete problem. The future works are to investigate satisfiability of (3,4)CNF formulas based on some results and properties of regular (3,4)bigraphs. As an example, we construct a minimal unsatisfiable (3,4)CNF formula from the followings MU(1) formula. 12345xxxxx? ? ? ?????? ? ? ?? ? ? ?? ? ? ???? ? ? ??? For each clause 12()LL? in 1 2 1 2 4 5 4 5{ ( ), ( ), ( ), ( )}x x x x x x x x? ? ? ? ? ? ? ? ? ?, we replace respectively the clause 12()LL? with the following form of formula by introducing ten new variables. 9 120123456789LLzzzzzzzzzz????? ? ? ?? ? ? ???? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ????????? The resulting formula is a minimal unsatisfiable formula containing 45 variables and 60 clauses. Hence, (15) (3, 4)MU CNF ??. We are interested in the result ( ) (3, 4)MU k CNF ??for those values of deficiencies k. References [1] and , Computer and IntractabilityA Guide to the Theory of NPCompleteness, and Company, San Francisco, 1979. [2] , , B?ning, An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF, Annals of Mathematics and Artificial Intelligence, 1998,23(34):229245. [3] , , , Polynomial time recognition of minimal unsatisfiable formulas with fixed clausevariable difference, Theoretical Computer Science, 2020,289(1):503516. [4] SPorschen, , and , On linear CNF formulas, in: , (eds.), Proceedings of the 19th International Conference on Theory and Applications of Satisfiability Testing (SAT2020), LNCS 4121, 2020, pp. 212225.(Springer, New York 2020). [5] , and , NPpleteness of SAT for restricted linear formulas classes, Proceedings of Guangzhou Symposium on Satisfiability in LogicBased Modeling, pp. 111123. [6] , , and , Linear CNF formulas and satisfiability, Discrete Applied Mathematics, 2020, 157(5):10461068. [7] , A simplified NPplete satisfiability problem, Discrete Applied Mathematics, 1984, 8(1):8589. [8] and , Co