完全问题及其不可近似外文翻译0503.doc

北方民族大学外文文献翻译译文题目 规则NP-完全问题及其不可近似性 原稿题目 A Reduction NP-complete Problems and Its Inapproximability原稿出处 the National Natural Science Foundation of China 系(部)名 称: 计算机科学与工程学院 学 生 姓 名: XXXX 专 业: 信息管理与信息系统 学 号: 20103279 指导教师姓名: 王晓峰 北方民族大学教务处制外文文献：A Reduction NP-complete Problems and Its InapproximabilityAbstract：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 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. 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 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 IntroductionLetbe the class of propositional formulas in conjunctive normal form. Aformulais a conjunction of clauses,. The setis the set of variables occurring in the formula. Denote as the number of clauses of F andas the number of variables occurring in. The deficiency of a formula F is defined as, denoted by.is the class offormulas with variables andclauses. A formulais minimal unsatisfiable () ifis unsatisfiable andis satisfiable for any clause. It is well known thatis not minimal unsatisfiable if 2. So, we denoteas the set of minimal unsatisfiable formulas with deficiency. Whether or not a formula belongs tocan be decided in polynomial time 3.In the transformation from aformula to a 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 complexity of satisfiability. In 4,5,6, the authors investigate satisfiability and structure of linearformulas, in which any two distinct clauses contain at most one common variable. C.R.Tovey presented simplified NP-complete 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, e.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 aformula to a linear formula by constructing minimal unsatisfiable formulas 12, and an effective algorithm for reducing k-to t-13.In this paper, we present a reduction from 3-formula to regular (3,4)-formula, where each clause contains exactly three literals, and each variable appears exactly fours times in a (3,4)-formula. Therefore, the problem (3,4)-is NP-complete, and then some properties of regular bigraphes will be helpful to investigate complexities of NP-hard problems. For a formulawith variables, the factor graph of is a bigraph, denote, where (called the set of variable nodes), (called the set of clause nodes), and the label functionis defined byif,if. The factor graph of a (3,4)-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)-formulas.2 Notations and basic gadgetsA literal is a propositional variable or a negated propositional variable. A clause is a disjunction of literals, , or a set of literals. A formula in conjunctive normal form () is a conjunction of clauses, , or a set of clauses, or a list of clauses. is the set of variables occurring in the formula. Denote as the number of clauses of and (or) as the number of variables occurring in. () denote the number of positive (negative) occurrences of variablein. The number of variableappearing indenoted as.In the paper, we always assume thatandfor any variablein formula. If (or), we can remove all clauses containing literal (or) from the original formula. So, we think that the conditionis default.We will use the following notations: The class offormulas withvariables andclauses.: The class offormulas, in which each clause contains exactlyliterals and each variable appears at mosttimes.: The class offormulas, in which each clause contains exactlyliterals and each variable appears exactlytimes.A formulawithvariablesincan be represented as the followingmatrix, called the representation matrix of, whereif, if, otherwise (or blank).The conjunction of formulasandis sometime written as. A formulaimplies that the subformulacontains no occurrence of variable, and.We will use the followingformulas as the gadget formula in reduction transformations.(1)Theformula. Its representation matrix is:We take a formula. Clearly, bothandare satisfiable, andand.Clearly, the subformulaofis satisfiable, and for any truth assignmentsatisfyingit holds that. The formulapresents a cycle of implications:.Remark 1: The formulacan be taken as a gadget formula to reduce the number of variables by replacing alloccurrences of a given variables within turn.(2)Theformulais defined by . The representation matrix of the formula is:Note that each variable in the formula appears exactly four times.Remark 2: The formulacan be taken as a gadget formula to long length of clause, or to add number of occurrence of variable.3 (3, 4)-SAT is NP-completeIn this section, we will show that a 3-formula can be reduced polynomial to a (3,4)-formula. Therefore, the problem (3,4)-is NP-complete.Letbe a 3-formula such that and for each variable.For a fixed variable, let.(1) Introduce a setof new variables, and define a formulaIt is corresponding to an implication cycle: .(2) Introduce setsof new variables, and define formulasand,Where the representation matrix ofis defined by(3) Define a formulaNote that the subformulacontains new clauses of length two, the subformula containsclauses of length three, and new variables appear exactly four times inrespectively, where.(4) Letbe a list of clauses of length two in, where. We introduce a setof new variables and a formulafor eachto long the length of, where the representation matrix ofis defined by(5) Define a formulaNote that the subformulacontainsclauses of length three, and each new variableappears exactly four times in, where.Lemma 1 The formulais satisfiable if and only ifis satisfiable.Proof: Letbe a truth assignment satisfying, and, where.Define an assignmentas follows:The assignment satisfies the formula.Conversely, we assume thatis a truth assignment satisfying. For each, the assignmentsatisfies following subformulas:The assignmentforceto be false, because the following formula is an unsatisfiable formula:We have thatfor. It requires thatmust satisfy each clause in.Specially, satisfies each clause in, it forces that. Therefore, we can construct an assignmentsatisfying. Based on the above method, we construct a formulastep by step:.By lemma 1, we have thatTheorem 1 The formulais satisfiable if and only ifis satisfiable.The formulahas the following characterizations:(1) Each clause contains exactly three literals, and each variable appears exactly four times in the formula.(2) and, where.Finally, we have that the problem (3,4)-is NP-complete by the NP-completeness of 3-.4 Inapproximability of MAX (3,4)-SATLetbe a 3-formula with variables. is the (3,4)-formulain section 3. We haveand.For an assignment, denote,andis maximum offor allassignments of variables in. We defineand.It is easy to get that for any assignmentover, there is an assignmentover, such that. So, we have thatand. It is implies that if a-fraction of the clauses ofis not satisfiable, then a-fraction of the clauses ofis not satisfiable.Hence, if one could distinguish in polynomial time between satisfiable (3,4)-formulas and (3,4)-formulas in which at most a (1-)-fraction of the clauses can be satisfied simultaneously, then one could distinguish in polynomial time between satisfiable 3-formulas and 3-formulas in which at most a (1-)-fraction of the clauses can be satisfied simultaneously.It is known that MAX 3-SATIS inapproximable 14, i.e., for any, the decision problem 3-is NP-hard, where 3-and3-.Therefore, we have that MAX (3,4)-SAT is inapproximable.5 Conclusions and future worksBased on the application of minimal unsatisfiable formulas, we have show that 3-SAT 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 NP-complete problem. The future works are to investigate satisfiability of (3,4)-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.For each clausein, we replace respectively the clausewith the following form of formula by introducing ten new variables.The resulting formula is a minimal unsatisfiable formula containing 45 variables and 60 clauses. Hence, . We are interested in the resultfor those values of deficiencies k.References1 M.R.Garey and D.S.Johnson, Computer and Intractability-A Guide to the Theory of NP-Completeness, W.H.Freeman and Company, San Francisco, 1979.2 G.Davydov, I.Davydova, H.Kleine Bning, An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF, Annals of Mathematics and Artificial Intelligence, 1998,23(3-4):229-245.3 H.Fleischner, O.Kullmann, S.Szeider, Polynomial time recognition of minimal unsatisfiable formulas with fixed clause-variable difference, Theoretical Computer Science, 2002,289(1):503-516.4 SPorschen, E.Speckenmeyer, and B.Randerath, On linear CNF formulas, in: A.Biere, C.P.Gomes(eds.), Proceedings of the 19th International Conference on Theory and Applications of Satisfiability Testing (SAT2006), LNCS 4121, 2006, pp. 212-225.(Springer, New York 2006).5 S.Porschen, and E.Speckenmeyer, NP-completeness of SAT for restricted linear formulas classes, Proceedings of Guangzhou Symposium on Satisfiability in Logic-Based Modeling, pp. 111-123.6 S.Porschen, E.Speckenmeyer, and X.Zhao, Linear CNF formulas and satisfiability, Discrete Applied Mathematics, 2009, 157(5):1046-1068.7 C.R.Tovey, A simplified NP-complete satisfiability problem, Discrete Applied Mathematics, 1984, 8(1):85-89.8 S.Hoory and S.Szeider, Computing unsatisfiable k-SAT instances with few occurrences per variables, Conference SAT2004, Vancouver, BC, Canada.9 S.Hoory and S.Szeider, Families of unsatisfiable k-CNF formulas with few occurrences per variables, arX e-Print Archive, Math. CO/041167, Nov. 2004.10 P.Savicky and J.Sgall, Note DNF tautologies with a limited number of occurrences of every variable, Theoretical Computer Science, 2000, 238(1-2):495-498.11 D.Xu, Applications of minimal unsatisfiable formulas to polynomially reduction formulas, Journal of Software, 2006, 17(5):1204-1212.12 D.Xu, T.Deng, and Q.Zhang, k-LSAT () is NP-complete, Journal of Software, 2008, 19(3):511-521.13 J.Wany and D.Xu, An effective algorithm for reducing k-CNF to t-CNF, Journal of Nanjing University Mathematical Biquarterly, 2005, 22(1):53-65.14 S.Arora and B.Barak, Computational complexity-A modern approach, Cambridge University Press, 2009.中文翻译：规则NP-完全问题及其不可近似性* 这项工作是由中国国家自然科学基金项目（编号：600863005）摘要：一个CNF公式可以用适当的还原转化,转化为具有一些特殊的结构和性质的另一个公式，使得两个公式具有相同的可满足性。CNF公式的因子图和常规结构有着一些良好的性质和显示结果的理论图，可用于研究它的可满足性和复杂性公式。极小不可满足公式有一个关键的特征，他本来就是不可满足的并且不是从原有的能满足的公式所转化过来的。我们提出了一个从3-CNF公式转化为（3,4）-CNF公式极其规则结构的多项式，其中每个子句包含三个字符，每个变量出现四次。因此,（3,4）-SAT是一个规则的NP-完全问题。我们重点研究（3,4）-CNF公式的可满足性，比如MAX（3,4）-SAT公式的不可近似性。关键词：规则，极小不可满足公式（3,4），CNF公式，常规结构，NP完全性1.引言 使CNF公式成为命题公式的合取范式的类。一个CNF公式F是一个结合的条款，。表示公式F的变量集。表示公式F的子句数，表示公式F变量发生数。公式F的缺陷被定义为，简记为。是CNF公式和变量n以及子句m结合的类。如果F是永无止境的并且满足任何，那么公式F是极小不可满足公式（MU）。众所周知，如果那么F就不是极小不可满足的 2 。所以，我们用MU（k）其中表示极小不可满足公式。可以在多项式中决定是否属于MU（k）。 从公式CNF到公式3-CNF的转变，我们发现极小不可满足公式的一些基本的应用。在公式和常规结构的类中，可能得到一些可满足性的特殊性质和复杂的结果。在4,5,6中，作者研究了可满足性和线性CNF公式结构，其中任何两个不同的条款包含在一个共同的变量。C.R.Tovey提出了简化的NP-完全可满足性问题，其中发生在公式变量个数有限 7 。在7、8、9、10中，作者研究发现可满足性和不可满足性的公式的变量很少出现在一起。 我们对可满足性和不可满足性的常规结构公式感兴趣，例如，精确长度的条款，发生的变量数，等等。我们发现，极小不可满足公式在减少一个给定的公式类成为常规公式方面具有重要应用11。我们已经介绍了一个简单的变换，通过构造极小不可满足公式减少到一个CNF公式12，并且有一个有效的算法用于降低k-to t-13。在本文中，我们提出了一个由3-CNF公式转化为（3,4）-CNF公式的规则，其中每个子句包含三个字符，每个变量在（3,4）-CNF公式中出现四次。因此，该问题是（3,4）-CNF是NP-完全问题，并且一些特性图将有助于探讨NP-难问题的复杂性。对于一个CNF公式，变量，F的因子图是一个偶图，表示为，（称为可变节点集），（称为第节点集），和标签函数由，其中，并且定义。公式（3,4）-CNF的因子图具有规则的结构，其中的变量节点的度是四，子句节点的度是三。因此，（3,4）-偶图的一些结果和性质可能对研究（3,4）-CNF公式有用。2.符号和基本工具 命题变量或者否定命题变量。一条子句C是一个析取文本，或者一组文本。公式F在(CNF)中的合取范式是结合的条款。，或一组条款或子句的列表。是在公式F中出现的变量集。表示条款的数目， （或） 作为F中出现的变量的数目。 () 表示F中的变量的正（负） 出现的次数。指变量出现次数。 在文件中，我们总是假设，和是对于任何变量。如果 （或），我们可以删除所有包含(或）从原始公式的条文。所以，我们认为条件是默认值。 我们将使用下列符号：CNF公式以及变量n和子句m的公式的类。：CNF公式的类，其中每一条款包含文字属于k并且每个变量出现的次数最多为b。：CNF公式的类，其中每一条款包含文字属于k并且每个变量只出现b次。一个公式中的变量n，属于可以表示为如下的矩阵，称为F的矩阵表示，如果，如果，否则（或空白）。公式和公式的连接，有时写为。一个公式意味着子公式中没有发生的变量，并且。我们将使用下面的公式为减少转换小工具公式。（1） 公式MU（2）它的表示矩阵：我们需要一个公式。显然和两者都是可满足的，和。显然，子公式对于可满足的，并且任何指令满足，。公式受一种周期公式的影响：。 注1：该公式可以作为一个小工具的公式给定的变量替换所有出现依次减少的变量的数量。（2）公式的定义是。该公式表示矩阵： 请注意，公式中的每个变量出现四次。 注2：该公式可以作为一个小工具公式子句的长度长，或添加的发生变化的数量。3.（3，4）-SAT是NP-完全问题 在本节中，我们将展示一个3-公式可以减少多项式变为（3,4）-公式。因此，该问题（3,4）-是NP-完全问题。让我们用作为一个3-公式的例子，并且用表示每个变量。对于一个固定的变量，让。（1）引入了一组新的变量，并定义一个公式它有一个对应的隐含周期：。（2）引入新的变量集，并定义公式和，由下列矩阵定义： （3）定义了一个公式注意，子公式包含新条款的长度，子公式包含条款，并且新的变量在出现正四次，其中。（4）让作为一个列表在的两个长度条款，其中。我们引进了一套新的变量和一个公式，并且每一个长度的属于，用矩阵表示为： （5）定义一个公式注意，子公式包含条长度为三的条款，每一个新的变量在出现四次，其中。引理1公式F是可满足的当且仅当是满足的。证明：让是一个正确的指令满足，并且，其中定义一个指令如下： 赋值满足公式。相反，我们认为是满足的正确指令。对于，每个指令满足以下子公式： 是错误的指令对于，因为公式不能满足下面的公式： 我们有对于。这就要求必须满足的每一条款。特别的，满足的每个条款，但是不满足。因此，我们可以构建一个指令满足。 基于以上方法，我们构建了一个公式： 我们可以由引理1得到。定理1 公式 F是可满足的当且仅当是满足的。该公式具有以下特征：（1）每个子句包含三个字符，每个变量出现在公式中四次。（2) 和其中最后，我们发现（3,4）-是NP-完整问题对于3-的NP-完整性。4. MAX (3,4)-SAT的不可近似性 假设是一个3-公式，公式变量。是第三