【正文】 3， 4） SAT 是 NP完全問題 在本節(jié)中，我們將 展示 一個 3CNF 公式可以減少多項式 變 為（ 3,4） CNF 公式。 （ 1） 公式 MU（ 2） 1 1 1 2 2 3 1 1 1( , , ) [ ( ) , ( ) , ( ) , , ( ) , ( ) , ( ) ]n n n n n n nA x x x x x x x x x x x x x x?? ? ? ? ? ? ? ? ? ? ? ? ? ? ?它的表示矩陣： 121nnxxxx?? ? ? ?????? ? ? ?????? ? ? ??? 我們需要一個公式 1 2 2 3 1 1[ ( ) , ( ) , , ( ) , ( ) ] n n nA x x x x x x x x?? ? ? ? ? ? ? ? ?。所以，我們認為 ( , ) ( , ) 1po s F x neg F x??條件是默認值。公式 F 在 (CNF)中的合取范式是結合的條款。我們已經(jīng)介紹了一個簡單的變換，通過構造極小不可滿足公式減少到一個 CNF 公式 [12]， 并且有 一個有效的算法用于降低 kCNF to tCNF [13]。 可以在多項式 中決定是否屬于 MU（ k） 。一個 CNF 公式 F 是一個結合的條款，1()mF C C? ? ? 。 1 中文 2760 字 外文文獻翻譯 譯文題目 規(guī)則 NP完全問題及其不可近似性 原稿題目 A Reduction NPplete Problems and Its Inapproximability 原稿出處 the National Natural Science Foundation of China 系 (部 )名 稱 : 計算機科學與工程學院 學 生 姓 名 : XXXX 專 業(yè) : 信息管理與信息系統(tǒng) 學 號 : 指導教師姓名 : 2 外文文獻： A Reduction NPplete Problems and Its Inapproximability Abstract： 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 theory of graph, which may be applied to investigating satisfiability and its plexity 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. We present a polynomial reduction from a 3CNF 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 NPplete problem. We focus on investigating satisfiability and 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, NPpleteness. 1 Introduction Let CNF be the class of propositional formulas in conjunctive normal form. A CNF formulaF is a conjunction of clauses, 1()mF C C? ? ? . The set ()varF is the set of variables occurring in the formulaF . Denote ( )clF as the number of clauses of F and ( )varF 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 nm is the class of CNF formulas withn variables andm clauses. A formulaF is minimal unsatisfiable (MU ) ifF is unsatisfiable and {}FC? is satisfiable for any clause CF? . It is well known thatF is not minimal unsatisfiable if ( ) 0dF? [2]. So, we denote ()MUk as the set of minimal unsatisfiable formulas with 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 3CNF formula [1], we find some basic applications of minimal unsatisfiable formulas. In classes of formulas with regular structures, one may get some special properties and results on plexity 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 mon variable. presented simplified 3 NPplete satisfiability problem, which the number of 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, ., 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 linear formula by constructing minimal unsatisfiable formulas [12], and an effective algorithm for reducing kCNF to tCNF [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 fours times in a (3,4) CNF formula. Therefore, the problem (3,4) CNF is NPplete, and then some properties of regular bigraphes will be helpful to investigate plexities of NPhard problems. For a CNF formula 1[ , , ]mF C C? with variables 1,nxx, the factor graph of F is a bigraph, denote ( , , , )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 oc c urs in C? and the label function : { 1, 1}E? ? ? ? is defined by ( , ) 1ijxC? ?? if ijxC? , ( , ) 1ijxC? ?? if ijxC?? . The factor graph of a (3,4)CNF formula has 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 propositional variable or a negated propositional variable. A clause C is a disjunction of literals, 1()mC L L? ? ? , or a set 1{ , , }mLLof literals. A formula F in conjunctive normal form ( CNF ) is a conjunction of clauses, 1()nF C C? ? ? , or a set 1{ , , }nCCof clauses, or a