規(guī)則np-完全問題及其不可近似性外文翻譯

1、<p><b>　　中文2760字 </b></p><p><b>　　外文文獻(xiàn)翻譯</b></p><p>　　譯文題目 規(guī)則NP-完全問題及其不可近似性 </p><p>　　原稿題目 A Reduction NP-complete Problems and Its Inappr

2、oximability</p><p>　　原稿出處 the National Natural Science Foundation of China </p><p>　　系(部)名 稱: 計(jì)算機(jī)科學(xué)與工程學(xué)院 </p><p>　　學(xué) 生 姓 名: XXXX

3、 </p><p>　　專 業(yè): 信息管理與信息系統(tǒng) </p><p>　　學(xué) 號(hào): </p><p>　　指導(dǎo)教師姓名: </p><p><b>　

4、　外文文獻(xiàn)：</b></p><p>　　A Reduction NP-complete Problems and Its Inapproximability</p><p>　　Abstract：A CNF formula can be transformed into another formula with some special structures or prope

5、rties 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, w

6、hich may be applied to investigating satisfiability and its complexity of formulas. The minimal unsatisfiable formulas have a critical characterization, which the formula itself is</p><p>　　Keywords: reducti

7、on, minimal unsatisfiability formula, (3,4)-CNF formula, regular structure, NP-completeness.</p><p>　　1 Introduction</p><p>　　Letbe the class of propositional formulas in conjunctive normal form

8、. 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 a

9、s, 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]</p&g

10、t;<p>　　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

11、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

12、simplified NP-complete satisfiability problem, which the number of variable</p><p>　　We are interested in satisfiability and unsatisfiability in some families of formulas with regular structures, e.g., exact

13、ly 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]. W

14、e have introduced a simple transformation to reduce aformula to a linear formula by constructing minimal unsatisfiable formulas [12], and an effective algorit</p><p>　　In this paper, we present a reduction f

15、rom 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 prop

16、erties 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 s

17、et of clause nodes), </p><p>　　2 Notations and basic gadgets</p><p>　　A literal is a propositional variable or a negated propositional variable. A clause is a disjunction of literals, , or a se

18、t 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 a

19、nd (or) as the number of variables occurring in. () denote the number of positive (negative) occurrences of variablein. The number of variableappearing ind</p><p>　　In the paper, we always assume thatandfor

20、 any variablein formula. If (or), we can remove all clauses containing literal (or) from the original formula. So, we think that the conditionis default.</p><p>　　We will use the following notations:</p&g

21、t;<p>　　: The class offormulas withvariables andclauses.</p><p>　　: The class offormulas, in which each clause contains exactlyliterals and each variable appears at mosttimes.</p><p>　　:

22、The class offormulas, in which each clause contains exactlyliterals and each variable appears exactlytimes.</p><p>　　A formulawithvariablesincan be represented as the followingmatrix, called the representati

23、on matrix of, whereif, if, otherwise (or blank).</p><p>　　The conjunction of formulasandis sometime written as. A formulaimplies that the subformulacontains no occurrence of variable, and.</p><p&g

24、t;　　We will use the followingformulas as the gadget formula in reduction transformations.</p><p>　　(1)Theformula. Its representation matrix is:</p><p>　　We take a formula. Clearly, bothandare sa

25、tisfiable, andand.</p><p>　　Clearly, the subformulaofis satisfiable, and for any truth assignmentsatisfyingit holds that. The formulapresents a cycle of implications:.</p><p>　　Remark 1: The for

26、mulacan be taken as a gadget formula to reduce the number of variables by replacing alloccurrences of a given variables within turn.</p><p>　　(2)Theformulais defined by . The representation matrix of the for

27、mula is:</p><p>　　Note that each variable in the formula appears exactly four times.</p><p>　　Remark 2: The formulacan be taken as a gadget formula to long length of clause, or to add number of

28、occurrence of variable.</p><p>　　3 (3, 4)-SAT is NP-complete</p><p>　　In this section, we will show that a 3-formula can be reduced polynomial to a (3,4)-formula. Therefore, the problem (3,4)-is

29、 NP-complete.</p><p>　　Letbe a 3-formula such that and for each variable.</p><p>　　For a fixed variable, let.</p><p>　　(1) Introduce a setof new variables, and define a formula</

30、p><p>　　It is corresponding to an implication cycle: .</p><p>　　(2) Introduce setsof new variables,, and define formulas</p><p><b>　　and,</b></p><p>　　Where th

31、e representation matrix ofis defined by</p><p>　　(3) Define a formula</p><p>　　Note that the subformulacontains new clauses of length two, the subformula containsclauses of length three, and new

32、 variables appear exactly four times inrespectively, where.</p><p>　　(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

33、the representation matrix ofis defined by</p><p>　　(5) Define a formula</p><p>　　Note that the subformulacontainsclauses of length three, and each new variableappears exactly four times in, wher

34、e.</p><p>　　Lemma 1 The formulais satisfiable if and only ifis satisfiable.</p><p>　　Proof: Letbe a truth assignment satisfying, and, where.</p><p>　　Define an assignmentas follows:

35、</p><p>　　The assignment satisfies the formula.</p><p>　　Conversely, we assume thatis a truth assignment satisfying. For each, the assignmentsatisfies following subformulas:</p><p>

36、　　The assignmentforceto be false, because the following formula is an unsatisfiable formula:</p><p>　　We have thatfor. It requires thatmust satisfy each clause in.</p><p>　　Specially, satisfies

37、each clause in, it forces that. Therefore, we can construct an assignmentsatisfying.</p><p><b>　　■</b></p><p>　　Based on the above method, we construct a formulastep by step:</p&g

38、t;<p><b>　　.</b></p><p>　　By lemma 1, we have that</p><p>　　Theorem 1 The formulais satisfiable if and only ifis satisfiable.</p><p>　　The formulahas the followin

39、g characterizations:</p><p>　　(1) Each clause contains exactly three literals, and each variable appears exactly four times in the formula.</p><p>　　(2) and, where.</p><p>　　Finally

40、, we have that the problem (3,4)-is NP-complete by the NP-completeness of 3-.</p><p>　　4 Inapproximability of MAX (3,4)-SAT</p><p>　　Letbe a 3-formula with variables. is the (3,4)-formulain sect

41、ion 3. We haveand.</p><p>　　For an assignment, denote,,andis maximum offor allassignments of variables in. We defineand.</p><p>　　It is easy to get that for any assignmentover, there is an assig

42、nmentover, 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.</p><p>　　Hence, if one could distinguish

43、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

44、3-formulas and 3-formulas in which at most a (1-)-fraction of the clauses can be satisfied simultaneously.</p><p>　　It is known that MAX 3-SATIS inapproximable [14], i.e., for any, the decision problem 3-is

45、NP-hard, where 3-and3-.</p><p>　　Therefore, we have that MAX (3,4)-SAT is inapproximable.</p><p>　　5 Conclusions and future works</p><p>　　Based on the application of minimal unsati

46、sfiable 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 i

47、s 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 (

48、3,4)-bigraphs.</p><p>　　As an example, we construct a minimal unsatisfiable (3,4)-CNF formula from the followings MU(1) formula.</p><p>　　For each clausein, we replace respectively the clausewit

49、h the following form of formula by introducing ten new variables.</p><p>　　The resulting formula is a minimal unsatisfiable formula containing 45 variables and 60 clauses. Hence, .</p><p>　　We a

50、re interested in the resultfor those values of deficiencies k.</p><p>　　References</p><p>　　[1] M.R.Garey and D.S.Johnson, Computer and Intractability-A Guide to the Theory of NP-Completeness,

51、W.H.Freeman and Company, San Francisco, 1979.</p><p>　　[2] G.Davydov, I.Davydova, H.Kleine B?ning, An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF, Annals of Mathematic

52、s and Artificial Intelligence, 1998,23(3-4):229-245.</p><p>　　[3] H.Fleischner, O.Kullmann, S.Szeider, Polynomial time recognition of minimal unsatisfiable formulas with fixed clause-variable difference, Th

53、eoretical Computer Science, 2002,289(1):503-516.</p><p>　　[4] SPorschen, E.Speckenmeyer, and B.Randerath, On linear CNF formulas, in: A.Biere, C.P.Gomes(eds.), Proceedings of the 19th International Conferen

54、ce on Theory and Applications of Satisfiability Testing (SAT2006), LNCS 4121, 2006, pp. 212-225.(Springer, New York 2006).</p><p>　　[5] S.Porschen, and E.Speckenmeyer, NP-completeness of SAT for restricted

55、linear formulas classes, Proceedings of Guangzhou Symposium on Satisfiability in Logic-Based Modeling, pp. 111-123.</p><p>　　[6] S.Porschen, E.Speckenmeyer, and X.Zhao, Linear CNF formulas and satisfiabilit

56、y, Discrete Applied Mathematics, 2009, 157(5):1046-1068.</p><p>　　[7] C.R.Tovey, A simplified NP-complete satisfiability problem, Discrete Applied Mathematics, 1984, 8(1):85-89.</p><p>　　[8] S

57、.Hoory and S.Szeider, Computing unsatisfiable k-SAT instances with few occurrences per variables, Conference SAT2004, Vancouver, BC, Canada.</p><p>　　[9] S.Hoory and S.Szeider, Families of unsatisfiable k-C

58、NF formulas with few occurrences per variables, arXiv.org e-Print Archive, Math. CO/041167, Nov. 2004.</p><p>　　[10] P.Savicky and J.Sgall, Note DNF tautologies with a limited number of occurrences of every

59、 variable, Theoretical Computer Science, 2000, 238(1-2):495-498.</p><p>　　[11] D.Xu, Applications of minimal unsatisfiable formulas to polynomially reduction formulas, Journal of Software, 2006, 17(5):1204-1

60、212.</p><p>　　[12] D.Xu, T.Deng, and Q.Zhang, k-LSAT () is NP-complete, Journal of Software, 2008, 19(3):511-521.</p><p>　　[13] J.Wany and D.Xu, An effective algorithm for reducing k-CNF to t-

61、CNF, Journal of Nanjing University Mathematical Biquarterly, 2005, 22(1):53-65.</p><p>　　[14] S.Arora and B.Barak, Computational complexity-A modern approach, Cambridge University Press, 2009.</p>&l

62、t;p><b>　　中文翻譯：</b></p><p>　　規(guī)則NP-完全問題及其不可近似性</p><p>　　摘要：一個(gè)CNF公式可以用適當(dāng)?shù)倪€原轉(zhuǎn)化,轉(zhuǎn)化為具有一些特殊的結(jié)構(gòu)和性質(zhì)的另一個(gè)公式，使得兩個(gè)公式具有相同的可滿足性。CNF公式的因子圖和常規(guī)結(jié)構(gòu)有著一些良好的性質(zhì)和顯示結(jié)果的理論圖，可用于研究它的可滿足性和復(fù)雜性公式。極小不可滿足公式有一個(gè)關(guān)鍵的特

63、征，他本來就是不可滿足的并且不是從原有的能滿足的公式所轉(zhuǎn)化過來的。我們提出了一個(gè)從3-CNF公式轉(zhuǎn)化為（3,4）-CNF公式極其規(guī)則結(jié)構(gòu)的多項(xiàng)式，其中每個(gè)子句包含三個(gè)字符，每個(gè)變量出現(xiàn)四次。因此,（3,4）-SAT是一個(gè)規(guī)則的NP-完全問題。我們重點(diǎn)研究（3,4）-CNF公式的可滿足性，比如MAX（3,4）-SAT公式的不可近似性。</p><p>　　關(guān)鍵詞：規(guī)則，極小不可滿足公式（3,4），CNF公式，常規(guī)結(jié)

64、構(gòu)，NP完全性</p><p><b>　　1.引言</b></p><p>　　使CNF公式成為命題公式的合取范式的類。一個(gè)CNF公式F是一個(gè)結(jié)合的條款，。表示公式F的變量集。表示公式F的子句數(shù)，表示公式F變量發(fā)生數(shù)。公式F的缺陷被定義為，簡(jiǎn)記為。是CNF公式和變量n以及子句m結(jié)合的類。如果F是永無止境的并且滿足任何，那么公式F是極小不可滿足公式（MU）。眾所周知，

65、如果那么F就不是極小不可滿足的[ 2 ]。所以，我們用MU（k）其中表示極小不可滿足公式?？梢栽诙囗?xiàng)式中決定是否屬于MU（k）。</p><p>　　從公式CNF到公式3-CNF的轉(zhuǎn)變，我們發(fā)現(xiàn)極小不可滿足公式的一些基本的應(yīng)用。在公式和常規(guī)結(jié)構(gòu)的類中，可能得到一些可滿足性的特殊性質(zhì)和復(fù)雜的結(jié)果。在[4,5,6]中，作者研究了可滿足性和線性CNF公式結(jié)構(gòu)，其中任何兩個(gè)不同的條款包含在一個(gè)共同的變量。C.R.Tove

66、y提出了簡(jiǎn)化的NP-完全可滿足性問題，其中發(fā)生在公式變量個(gè)數(shù)有限[ 7 ]。在[7、8、9、10 ]中，作者研究發(fā)現(xiàn)可滿足性和不可滿足性的公式的變量很少出現(xiàn)在一起。</p><p>　　我們對(duì)可滿足性和不可滿足性的常規(guī)結(jié)構(gòu)公式感興趣，例如，精確長度的條款，發(fā)生的變量數(shù)，等等。我們發(fā)現(xiàn)，極小不可滿足公式在減少一個(gè)給定的公式類成為常規(guī)公式方面具有重要應(yīng)用[11]。我們已經(jīng)介紹了一個(gè)簡(jiǎn)單的變換，通過構(gòu)造極小不

67、可滿足公式減少到一個(gè)CNF公式[12]，并且有一個(gè)有效的算法用于降低k-to t-[13]。</p><p>　　在本文中，我們提出了一個(gè)由3-CNF公式轉(zhuǎn)化為（3,4）-CNF公式的規(guī)則，其中每個(gè)子句包含三個(gè)字符，每個(gè)變量在（3,4）-CNF公式中出現(xiàn)四次。因此，該問題是（3,4）-CNF是NP-完全問題，并且一些特性圖將有助于探討NP-難問題的復(fù)雜性。對(duì)于一個(gè)CNF公式，變量，F(xiàn)的因子圖是一個(gè)偶圖，表示為，（

68、稱為可變節(jié)點(diǎn)集），（稱為第節(jié)點(diǎn)集），和標(biāo)簽函數(shù)由，其中，并且定義。公式（3,4）-CNF的因子圖具有規(guī)則的結(jié)構(gòu)，其中的變量節(jié)點(diǎn)的度是四，子句節(jié)點(diǎn)的度是三。因此，（3,4）-偶圖的一些結(jié)果和性質(zhì)可能對(duì)研究（3,4）-CNF公式有用。</p><p><b>　　2.符號(hào)和基本工具</b></p><p>　　命題變量或者否定命題變量。一條子句C是一個(gè)析取文本，，或者一組

69、文本。公式F在(CNF)中的合取范式是結(jié)合的條款。，或一組條款或子句的列表。是在公式F中出現(xiàn)的變量集。表示條款的數(shù)目， （或） 作為F中出現(xiàn)的變量的數(shù)目。 () 表示F中的變量的正（負(fù)） 出現(xiàn)的次數(shù)。指變量出現(xiàn)次數(shù)。</p><p>　　在文件中，我們總是假設(shè)，和是對(duì)于任何變量。如果 （或），我們可以刪除所有包含(或）從原始公式的條文。所以，我們認(rèn)為條件是默認(rèn)值。</p><p>　　我們

70、將使用下列符號(hào)：</p><p>　?。篊NF公式以及變量n和子句m的公式的類。</p><p>　?。篊NF公式的類，其中每一條款包含文字屬于k并且每個(gè)變量出現(xiàn)的次數(shù)最多為b。</p><p>　?。篊NF公式的類，其中每一條款包含文字屬于k并且每個(gè)變量只出現(xiàn)b次。</p><p>　　一個(gè)公式中的變量n，屬于可以表示為如下的矩陣，，稱為F

71、的矩陣表示，如果，如果，否則（或空白）。</p><p>　　公式和公式的連接，有時(shí)寫為。一個(gè)公式意味著子公式中沒有發(fā)生的變量，并且。</p><p>　　我們將使用下面的公式為減少轉(zhuǎn)換小工具公式。</p><p><b>　　公式MU（2）</b></p><p><b>　　它的表示矩陣：</b>

72、;</p><p>　　我們需要一個(gè)公式。顯然和兩者都是可滿足的，和。</p><p>　　顯然，子公式對(duì)于可滿足的，并且任何指令滿足，。公式受一種周期公式的影響：。</p><p>　　注1：該公式可以作為一個(gè)小工具的公式給定的變量替換所有出現(xiàn)依次減少的變量的數(shù)量。</p><p>　　（2）公式的定義是。該公式表示矩陣：</p>

73、;<p>　　請(qǐng)注意，公式中的每個(gè)變量出現(xiàn)四次。</p><p>　　注2：該公式可以作為一個(gè)小工具公式子句的長度長，或添加的發(fā)生變化的數(shù)量。</p><p>　　3.（3，4）-SAT是NP-完全問題</p><p>　　在本節(jié)中，我們將展示一個(gè)3-公式可以減少多項(xiàng)式變?yōu)椋?,4）-公式。因此，該問題（3,4）-是NP-完全問題。</p>

74、<p>　　讓我們用作為一個(gè)3-公式的例子，并且用表示每個(gè)變量。</p><p>　　對(duì)于一個(gè)固定的變量，讓。</p><p>　?。?）引入了一組新的變量，并定義一個(gè)公式</p><p>　　它有一個(gè)對(duì)應(yīng)的隱含周期：。</p><p>　?。?）引入新的變量集，并定義公式和，由下列矩陣定義：</p><p&

75、gt;　?。?）定義了一個(gè)公式</p><p>　　注意，子公式包含新條款的長度，子公式包含條款，并且新的變量在出現(xiàn)正四次，其中。</p><p>　?。?）讓作為一個(gè)列表在的兩個(gè)長度條款，其中。我們引進(jìn)了一套新的變量和一個(gè)公式，并且每一個(gè)長度的屬于，用矩陣表示為：</p><p><b>　?。?）定義一個(gè)公式</b></p>

76、<p>　　注意，子公式包含條長度為三的條款，每一個(gè)新的變量在出現(xiàn)四次，其中。</p><p>　　引理1公式F是可滿足的當(dāng)且僅當(dāng)是滿足的。</p><p>　　證明：讓是一個(gè)正確的指令滿足，并且，其中</p><p><b>　　定義一個(gè)指令如下：</b></p><p><b>　　賦值滿足公式。

77、</b></p><p>　　相反，我們認(rèn)為是滿足的正確指令。對(duì)于，每個(gè)指令滿足以下子公式：</p><p>　　是錯(cuò)誤的指令對(duì)于，因?yàn)楣讲荒軡M足下面的公式：</p><p>　　我們有對(duì)于。這就要求必須滿足的每一條款。</p><p>　　特別的，滿足的每個(gè)條款，但是不滿足。因此，我們可以構(gòu)建一個(gè)指令滿足。</p>

78、<p>　　基于以上方法，我們構(gòu)建了一個(gè)公式：</p><p>　　我們可以由引理1得到。</p><p>　　定理1 公式 F是可滿足的當(dāng)且僅當(dāng)是滿足的。</p><p>　　該公式具有以下特征：</p><p>　?。?）每個(gè)子句包含三個(gè)字符，每個(gè)變量出現(xiàn)在公式中四次。</p><p><b&g

79、t;　?。?) 和</b></p><p><b>　　其中</b></p><p>　　最后，我們發(fā)現(xiàn)（3,4）-是NP-完整問題對(duì)于3-的NP-完整性。</p><p>　　4. MAX (3,4)-SAT的不可近似性</p><p>　　假設(shè)是一個(gè)3-公式，公式變量。是第三節(jié)的（3,4）-公式。我們有和

80、。</p><p>　　對(duì)于指令。定義，并且表示F中關(guān)于的最大的變量。定義和。</p><p>　　它是容易的，對(duì)于的任何指令，有屬于，如。所以，我們有和。這意味著，如果F的一部分條款是不滿足的，那么一部分條款對(duì)于F是不可滿足的。</p><p>　　因此，如果能同時(shí)滿足多項(xiàng)式（3,4）-CNF公式和（3,4）-CNF多項(xiàng)式的大部分條款1- ，那么就是可滿足的，如果

81、能同時(shí)滿足（3，4）-CNF公式和（3，4）-CNF多項(xiàng)式的大部分條款1-，那么也是可滿足的。</p><p>　　它是已知的最大MAX 3-SATIS 不可近似性[ 14 ]，i.e,對(duì)于任何，3-問題是是NP-難的，其中3-并且3-</p><p>　　因此，我們MAX (3,4)-SAT是不可近似性的。</p><p>　　5.結(jié)論和未來的工作<

82、;/p><p>　　基于極小不可滿足公式的應(yīng)用，我們已經(jīng)表明，可以減少3-SAT問題的多項(xiàng)式（3,4）-SAT。下面（3,4）-CNF公式具有規(guī)則結(jié)構(gòu)，其中的因子圖是一個(gè)普通的（3,4）-偶圖，變量節(jié)點(diǎn)度是四，第節(jié)點(diǎn)的度正是三。因此，我們得到一個(gè)正規(guī)的NP-完全問題。未來的工作是探討（3,4）-CNF基于一些結(jié)果和公式（3,4）-偶圖的性質(zhì)。</p><p>　　作為一個(gè)例子，我們構(gòu)建了一個(gè)極

83、小不可滿足的（3,4）-CNF計(jì)算公式從以下的MU(1)公式。</p><p>　　每個(gè)子句都在中，我們將分別用下列公式的形式引入十個(gè)新變量的條款。</p><p>　　所得到的公式是一個(gè)包含45個(gè)變量和60條款的極小不可滿足公式。因此有。我們對(duì)中不滿足k的結(jié)果感興趣.</p><p><b>　　參考文獻(xiàn)</b></p><

84、;p>　　[ 1 ] M.R.Garey和D.S.Johnson，計(jì)算機(jī)不可近似性-A指南和NP-完全性理論，W.H.Freeman公司，舊金山，1979。</p><p>　　[ 2]G.Davydov, I.Davydova, H.Kleine B?ning，一種為CNF的極小不可滿足問題的一種有效算法，人工智能數(shù)學(xué)年刊，1998,23（3-4）：229-245。</p><

85、;p>　　[ 3 ] H.Fleischner, O.Kullmann, S.Szeider，極小不可滿足公式的固定條款變量差分多項(xiàng)式時(shí)間識(shí)別，計(jì)算機(jī)科學(xué)理論，20022 89（1）：503-516。</p><p>　　[ 4 ] SPorschen, E.Speckenmeyer, and B.Randerath,線性CNF公式，A.BIERE，C.P.Gomes（主編），對(duì)可滿足性

86、測(cè)試的理論與應(yīng)用第十九屆國際會(huì)議（sat2006），LNCS 4121，2006，頁212-225。（施普林格出版社，紐約2006）。</p><p>　　[ 5 ]美國Porschen，和E.Speckenmeyer，NP完全性的SAT約束線性公式的類別，廣州可滿足性邏輯會(huì)議建模，111-123頁。</p><p>　　[ 6 ]美國Porschen，E. Speck

87、enmeyer，X.趙，線性CNF公式和可滿足性，離散應(yīng)用數(shù)學(xué)，2009，157（5）：1046-1068。</p><p>　　[ 7 ]C.R.Tovey，一個(gè)簡(jiǎn)化的NP-完全可滿足性問題，離散數(shù)學(xué)應(yīng)用，1984，8（1）：85-89。</p><p>　　[ 8 ]美國Hoory和美國Szeider永無止境的K-SAT實(shí)例，計(jì)算每個(gè)變量， sat2004會(huì)議，BC，溫哥華，加拿大。&

88、lt;/p><p>　　[ 9 ]美國hoory和美國szeider，永無止境的K-CNF公式與每個(gè)變量，arXiv.org電子預(yù)印本系統(tǒng)，數(shù)學(xué)。CO／041167，11月2004。</p><p>　　[ 10 ]P.Savicky和J.Sgall，注意未完成重言式與有限數(shù)量的每個(gè)變量的出現(xiàn)，理論計(jì)算機(jī)科學(xué)，2000，238（1-2）：495-498。</p><p>

89、;　　[11]D.徐，極小不可滿足公式多項(xiàng)式公式的應(yīng)用，軟件學(xué)報(bào)，2006，17（5）：1204-1212。</p><p>　　[12]D.徐，T.鄧，和張，k-LACS（）是NP完全問題，軟件學(xué)報(bào)，2008，19（3）：511-521。</p><p>　　[13] J.溫妮和D.徐，從k-CNF到t-CNF歸約的一種有效算法，南京大學(xué)學(xué)報(bào)數(shù)學(xué)半年刊，2005，22（1）：5