规则np-完全问题及其不可近似性外文翻译(编辑修改稿)

规则np-完全问题及其不可近似性外文翻译(编辑修改稿)内容摘要：

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。