1、 1 中文 2760 字 外文文献翻译 译文题目 规则 NP-完全问题及其不可近似性 原稿题目 A Reduction NP-complete Problems and Its Inapproximability 原稿出处 the National Natural Science Foundation of China 系 (部 )名 称 : 计算机科学与工程学院 学 生 姓 名 : XXXX 专 业 : 信息管理与信息系统 学 号 : 指导教师姓名 : 2 外文文献： A Reduction NP-complete Problems and Its Inapproximability Abs
2、tract： A CNF formula can be transformed into another formula with some special structures or properties by a proper reduction transformation, such that two formulas have the same satisfiability. The factor graphs of CNF formulas with regular structures have some well properties and known results in
3、theory of graph, which may be applied to investigating satisfiability and its complexity of formulas. The minimal unsatisfiable formulas have a critical characterization, which the formula itself is unsatisfiable and the resulting formula moving anyone clause from the original formula is satisfiable
4、. We present a polynomial reduction from a 3-CNF formula to a (3,4)-CNF formula with regular structure, which each clause contains exactly three literals, and each variable appear exactly four times. Therefore, (3,4)-SAT is a regular NP-complete problem. We focus on investigating satisfiability and
5、properties of (3,4)-CNF formulas, such as inapproximability of MAX (3,4)-SAT. Keywords: reduction, minimal unsatisfiability formula, (3,4)-CNF formula, regular structure, NP-completeness. 1 Introduction LetCNF be the class of propositional formulas in conjunctive normal form. ACNF formulaF is a conj
6、unction of clauses, 1()mF C C . The set ()varF is the set of variables occurring in the formulaF . Denote# ( )cl F as the number of clauses of F and # ( )var F as the number of variables occurring in F . The deficiency of a formula F is defined as # ( ) # ( )cl F var F , denoted by ()dF . ( , )CNF n
7、 m is the class ofCNF formulas withn variables andm clauses. A formulaF is minimal unsatisfiable (MU ) ifF is unsatisfiable and FC is satisfiable for any clauseCF . It is well known thatF is not minimal unsatisfiable if ( ) 0dF 2. So, we denote ()MUk as the set of minimal unsatisfiable formulas with
8、 deficiency 1k . Whether or not a formula belongs to ()MUk can be decided in polynomial time 3. In the transformation from a CNF formula to a 3-CNF formula 1, we find some basic applications of minimal unsatisfiable formulas. In classes of formulas with regular structures, one may get some special p
9、roperties and results on complexity of satisfiability. In 4,5,6, the authors investigate satisfiability and structure of linear CNF formulas, in which any two distinct clauses contain at most one common variable. C.R.Tovey presented simplified 3 NP-complete satisfiability problem, which the number o
10、f variables occurring in formulas were bounded 7. In 7,8,9,10, the authors investigated satisfiability and unsatisfiability in some families of formulas with few occurrences of variables. We are interested in satisfiability and unsatisfiability in some families of formulas with regular structures, e
11、.g., exactly length of clauses, number of occurrence of variables, and so on. We find that the minimal unsatisfiable formulas have important applications in reducing a given class of formulas to a class of regular formulas 11. We have introduced a simple transformation to reduce a CNF formula to a l
12、inear formula by constructing minimal unsatisfiable formulas 12, and an effective algorithm for reducing k-CNF to t-CNF 13. In this paper, we present a reduction from 3-CNF formula to regular (3,4)-CNF formula, where each clause contains exactly three literals, and each variable appears exactly four
13、s times in a (3,4)- CNF formula. Therefore, the problem (3,4)- CNF is NP-complete, and then some properties of regular bigraphes will be helpful to investigate complexities of NP-hard problems. For a CNF formula 1 , , mF C C with variables 1,nxx , the factor graph of F is a bigraph, denote ( , , , )
14、F var clG V V E , where 1 , , var nV x x (called the set of variable nodes), 1 , , cl mV C C (called the set of clause nodes), ( , ) : i j i jE x C x o c c u r s i n C and the label function : 1, 1E is defined by ( , ) 1ijxC if ijxC , ( , ) 1ijxC if ijxC . The factor graph of a (3,4)-CNF formula has
15、 a regular structure, in which the degree of variable node is exactly four, the degree of clause node is exactly three. Therefore, some results and properties of regular (3,4)-bigraphs may be useful for investigating satisfiability of (3,4)-CNF formulas. 2 Notations and basic gadgets A literal is a
16、propositional variable or a negated propositional variable. A clause C is a disjunction of literals, 1()mC L L , or a set 1 , , mLL of literals. A formula F in conjunctive normal form ( CNF ) is a conjunction of clauses, 1()nF C C , or a set 1 , , nCC of clauses, or a list 1 , , nCC of clauses. ()va
17、rF is the set of variables occurring in the formulaF . Denote # ( )cl F as the number of clauses of F and # ( )var F (or| ( )|var F ) as the number of variables occurring inF . ( , )pos F x ( ( , )neg F x ) denote the number of positive (negative) occurrences of variablex inF . The number of variablex appearing inF denoted as ( , ) ( , ) ( , )o c c s F x p o s F x n e g F x. In the paper, we always assume that ( , ) 1pos F x and ( , ) 1neg F x for any variablex in formulaF .
