可满足实例的归结复杂度

沈静，梅丹

海军工程大学应用数学系，武汉 430033

可满足实例的归结复杂度

沈静，梅丹

海军工程大学应用数学系，武汉 430033

1 引言

约束满足问题（Constraint Satisfaction Problem，CSP）由变量有限集合、值域集合、约束集合组成，通过为一组变量赋值来满足一组给定的约束。约束满足问题在人工智能、计算机科学等众多应用领域都具有十分重要的意义。近年来，通过大量的实验研究人们发现，在一些随机CSP模型中，随着控制参数r的变化，当变量个数n充分大时，存在某个临界值r*，使得当r＜r*时，CSP模型产生的实例可满足的概率趋近于1；而当r＞r*时，CSP模型产生的实例可满足的概率趋近于0，人们称此现象为相变现象，称临界值r*为“相变点”。随着控制参数r的增加，求解实例的难度也发生了从易到难再到容易的变化，最难解的实例正好位于相变点附近。相变现象和算法分析之间的相关问题引起了国内外学者的极大关注[1-3]。

为了刻画求解CSP模型实例的难度，人们对各种CSP模型的归结复杂度进行分析[4-7]。归结法是一种证明SAT实例不可满足性的系统，其树型归结证明的长度与DPLL算法的运行时间有密切关系。1988年，Chvatal等人[8]证明了含有n个变量，cn个子句的随机k-SAT问题在k≥3的情况下，具有指数级别的树型归结证明，故基于DPLL算法求解随机k-SAT问题所花费的时间呈指数增长。2002年，Mitchell[9]按照一定的编码规则，把一般CSP实例转化为SAT实例，把转化的SAT实例的归结复杂度作为CSP实例的归结复杂度，指出了如果实例对于归结证明系统是难解的，则对基于归结的算法也是难解的。

GRB模型[10]是近年来新提出的一种CSP模型，是RB模型[11-13]的推广。它具有精确的可满足相变现象，相变点r*=1。当r＞1时，随着变量个数n趋近于无穷大，GRB模型的实例是不满足的概率趋近于1，GRB模型的不可满足实例对于树型归结证明具有指数下界[10]。当r＜1时，GRB模型的实例是可满足的概率趋近于1，实验显示在相变点附近产生的可满足实例也是难解的，如何刻画可满足实例的难解性?本文利用Achlioptas等人提出的方法[14]证明了：对于GRB模型在相变点附近产生的可满足实例随机选取一定的变量赋值，在求解过程中以很高的概率得到一个不可满足的子问题，其子问题的归结复杂度为2Ω(n)，因此从理论上证明了GRB模型在相变点附近产生的可满足实例基于归结的算法都是难解的。

2 GRB模型的定义

约束满足问题以三元组I=(X,D,C)来描述约束满足问题产生的实例，其中X=(x1,x2,…,xn)是n个变量的集合；值域D=(D1,D2,…,Dn)是X中各变量取值的集合；C=(C1,C2,…,Ct)是约束集合，且Ci=(Xi,Ri)，这里Xi=(xi1,xi2,…,xiki)是变量集合X的子集，其长度为ki，称为约束作用域；Ri是Di1×Di2×…×Diki的子集，称为约束关系。

设A=D1×D2×…×Dn，(a1,a2,…,an)∈A称为X的一个赋值，即X中的每个变量都取定值域内的一个值。若(a1,a2,…,an)∈A满足所有的约束，则称这个赋值是可满足的，否则称这个赋值是不可满足的。如果实例I存在可满足的赋值，则称实例I是可满足的，否则称实例I是不可满足的。

设T是一个集合，|T|表示T中所含元素的个数。定义Ω(n)={f(n)：存在常数c＞0，使得f(n)≥cn}。如果n→∞时，事件εn成立的概率趋近于1，称事件εn是几乎成立的。

第1步：随机可重复地选取长度为k的变量子集Xi=(xi1,xi2,…,xik)作为约束作用域。

第2步：随机可重复地从Di1×Di2×…×Dik选取Ri作为约束关系，其中|Ri|=pdk，0＜p＜1。

理论上已经证明了GRB模型存在精确的相变现象。

3 归结法

给定一个CNF公式F和子句C，如果存在一个子句序列π={C1,C2,…,Cm=C}，∀Ci∈π，要么Ci∈F，要么Ci是由Cj和Ck(j,k≤i)基于以下规则推导出来的：

其中A和B是子句，x是一个命题变量，称π是由CNF公式F推导出子句C的一个归结。由CNF公式推导出空子句（记空子句为□）的归结称为公式F的归结反演。

以π中的子句作为顶点，若Ci是由Cj和Ck推导出来的，则Ci和Cj，Ci和Ck之间分别用边连接，这样得到的图Gπ如果是树，则称π是由CNF公式F推导出子句C的树型归结。

定义2（宽度）称子句C中出现变量的个数为子句C的宽度，记作ω(C)。称公式F中所有子句的最大宽度为公式F的宽度，记作ω(F)。称归结π中所有子句的最大宽度为π的宽度，记作ω(π)。称所有由公式F推导出子句C的归结π的最小宽度为由公式F推导出子句C的归结宽度，记作ω(F⇒C)。

定义3（归结复杂度）设π={C1,C2,…,Cm=□}是由公式F推导出空子句□的归结，记

称Res(F)为公式F的归结复杂度。

定义4（子句复杂度）设π={C1,C2,…,Cm=C}是由公式F推导出子句C的归结，μ(C)表示推出C的最小的子问题中所含变量的个数，称μ(C)为子句C的复杂度。

定义5（自由变量）设P是实例I的子问题，给定变量x，P-x是子问题P中去掉含有变量x的约束后剩下的问题，如果任意满足P-x的赋值能扩展为满足子问题P的赋值，则变量x称为自由变量。B(P)为P中所有自由变量的集合。

定义6（度）称包含变量x的约束个数为变量x的度，记为deg（x）。

公式F是不可满足的当且仅当公式F存在一个归结反演。

Mitchell按照如下的编码规则，把SAT实例的归结复杂度推广到一般的CSP实例。

（2）冲突子句：指每个约束中规定的不可满足的赋值组。

（3）至多一个取值子句：指一个变量一次至多从值域中取一个值。

按照上述Mitchell规则构造相应的CNF公式，记为CNF（I）。公式CNF（I）有可满足赋值当且仅当实例I有可满足赋值。如果实例I有可满足赋值，当xi=j时，设置xij=True，这样可相应地产生公式CNF（I）的可满足赋值。反之，若公式CNF（I）有一个可满足赋值，当xij=True时，设置xi=j，可相应地产生实例I的可满足赋值。称公式CNF（I）的归结复杂度Res（CNF（I））为实例I的归结复杂度。

4 GRB模型可满足实例的归结复杂度

GRB模型的不可满足实例对于树型归结证明具有指数下界[10]。当控制参数r＜1，GRB模型随机产生的实例I几乎是可满足的，实验显示在相变点附近产生的可满足实例是难解的。由于归结证明是针对不可满足实例而言的，但下面的引理证明了随机选取θn个变量赋值后剩下的子问题P几乎是不可满足的，因此GRB模型的可满足实例的归结复杂度可转换为子问题P的归结复杂度。

引理1[5]设F为一个含有n个变量的CNF公式，若C为空子句□，则Res(F)≥2w(F⇒C)-w(F)。

由引理1可知，要证明CNF公式F的归结复杂度为2Ω(n)，只需证明w(F⇒□)=Ω(n)。进一步，由归结宽度的定义，只需证明在归结反演中存在子句C，使得w(C)=Ω(n)。

定理3θ＞0，当1-θ＜r＜1时，设I是由GRB模型随机产生的实例，随机从n个变量中选取θn个变量赋值，赋值后剩下的子问题P几乎没有归结复杂度小于2Ω(n)的树型归结证明。

证明设I是由GRB模型生成的一个随机实例，GRB模型已经证明了下面两个结论[10]：

假设存在含有s≤cn的子问题是不可满足的，因此可得一个最小不可满足的子问题I1，含有变量的个数s≤cn，由（1）知，子问题I1中至多有βslnd个约束。因此在I1中存在一个变量x，其度不超过kβlnd。由于I1是最小不可满足的子问题，则I1-x是可满足的，由（2）知变量x是自由变量，任意满足I1-x的赋值能扩展为满足子问题I1的赋值，与I1是最小不可满足的子问题矛盾，故含有s≤cn的子问题是可满足的。

Mitchell已经证明了，对于实例I，如果至多有s个变量的子问题是可满足的，则I的每个归结反演中存在一个满足s/2≤μ(C)≤s的子句C[9]。

设实例I对应的CNF公式为CNF（I），由于含有s≤cn的子问题是可满足的，在CNF（I）中存在子句C，其复杂度满足cn/2≤μ(C)≤cn。设P1是使得CNF（P1）推导出子句C的最小子问题，故P1中至少有cn/2个变量，至多有cn个变量。由（1）知，P1中至多有βcnlnd个约束，至多有cn/3个变量的度大于3kβlnd。假设在P1中有变量x，如果变量x的度满足deg(x)＜3kβlnd，由（2）知变量x是P1的自由变量。从P1中移去变量x和含变量x的约束，得到子问题P2，由P1的极小性，可得CNF（P2）不能推导出C，故能找到满足P2但不满足C的赋值Tx。若变量x的任何值域变量不出现在子句C中，则变量x的任何赋值都不影响C。由于赋值Tx不满足C，故变量x的任何赋值都不满足CNF（P1），与变量x是P1的自由变量矛盾，故变量x至少有一个值域变量出现在子句C中，即度不超过3kβlnd的变量都包含在子句C，则子句C的宽度满足w(C)≥cn/2-cn/3=cn/6。因此P1中含有度不超过3kβlnd的变量至少有cn/6个。

取0＜θ＜c/6，对实例I随机从n个变量中选取θn个变量赋值，P为赋值后的子问题，由定理1知P是不可满足的。设赋值后P1剩下的子问题为超过3kβlnd的变量至少有个，类似上面的证明，度不超过3kβlnd的变量都包含在子句C中，因此由引理1可得子问题P几乎没有归结复杂度小于2Ω(n)的树型归结证明。

5 结束语

由于在搜索解的过程中，产生了需要花很长时间求解的不可满足的子问题，因此可将求解可满足实例的难度和求解其不可满足的子问题的难度联系在一起，从理论上证明了GRB模型在相变点附近产生的可满足实例在对θn个变量赋值后产生的子问题都是不可满足的，这些不可满足的子问题对于树型归结证明具有指数下界，因此用树型归结证明判定这些子问题的不可满足性需要花指数级别的时间，由此证明了GRB模型在相变点附近产生的可满足实例对基于归结到算法是难解的。由于测试局部搜索算法需要可满足的实例[13，15]，因此GRB模型在相变点附近产生的可满足实例可作为测试局部搜索算法的平台。

[1]CheesmanP，KanefskyB，Taylor W.Wherethereally hardproblems are[C]//Proceedings of IJCAI-91，1991：331-337.

[2]Mitchell D.Hard problems for CSP Algorithms[C]//Proceedings of 15th National Conf on Artificial Intelligence（AAAI-98），1998：398-405.

[3]Achlioptas D，Naor A，Peres Y.Rigorous location of phase transitions in hard optimization prolems[J].Nature，2005，435（7043）：759-764.

[4]Beame P，Karp R，Pitassi T，et al.The efficiency of resolutionandDavis-Putnamprocedures[J].SIAMJournal on Computing，2002，31（4）：1048-1075.

[5]Ben-Sasson E，Wigderson A.Short proofs are narrow-resolution made simple[J].Journal of ACM，2001，48（10）：149-169.

[6]Gao Y，Culberson J.Resolution complexity of random constraint satisfaction problems：Another half of the story[J]. Discrete Applied Mathematics，2005，153（1/3）：124-140.

[7]Molloy M，Salavatipour M R.The resolution complexity ofrandomconstraintsatisfactionproblems[J].SIAM，2007，7（3）：895-922.

[8]Chvatal V，Szemeraedi E.Many hard examples for resolution[J].Journal of the ACM，1988，35（4）：759-208.

[9]Mitchell D.Resolution complexity of random constraints[C]// Proceedings of the Eighth International Conference on Principles and Practices of Constraint Programming，Ithaca，NewYork，2002.

[10]ShenJ，Li L.Resolutioncomplexityof randomconstraint satisfaction problems with non-constant domain size[J].Journal of Information and Computational Science，2011，8（16）：4149-4156.

[11]Xu K，Li W.Exact phase transitions in random constraint satisfaction problems[J].Journal of Artificial Intelligence Reseach，2001，12（1）：93-103.

[12]Xu K，Li W.Many hard examples in exact phase transition[J].Theoretical Computer Science，2006，355（3）：291-302.

[13]Xu K，Boussemart F，Hemery F，et al.Random constrint satisfaction：Easy generation of hard satifiable instances[J]. Artificial Intelligence，2007，171（8/9）：514-534.

[14]Achlioptas D，Beame P，Molloy M.Exponential bounds for DPLL below the satisfiability threshold[C]//Proc 15th ACM-SIAM Symp Discrete Algorithms，2004：132-133.

[15]Achlioptas D，Gomes C，Kautz H，et al.Generating satisfiable probleminstances[C]//Proceedings of AAAI-00，2000：256-301.

SHEN Jing,MEI Dan

Department of Applied Mathematics,Naval University of Engineering,Wuhan 430033,China

The model GRB is a random model of constraint satisfaction problem,and it exhibits exact solubility phase transitions.For the experimental results that the satisfiability instances in the phase transition region are hard to solve,it uses the relation between the clause width and the resolution complexity to prove that almost all satisfiability instances of the model GRB have no tree-like resolution proofs of length less than exponential size.Therefore it shows theoretically that the satisfiability instances in the phase transition region are hard for the algorithms based on resolution.

resolution complexity;constraint satisfaction problem（CSP）;solubility phase transition

GRB模型是一种随机约束满足问题模型，此模型具有精确的可满足相变现象。针对实验中出现的GRB模型在相变区域产生的可满足实例都是难解的现象，利用子句宽度和归结复杂度的关系证明了GRB模型在相变点附近产生的可满足实例对于树型归结证明具有指数下界。因此从理论上证明了在相变区域产生的可满足实例对基于归结的算法是难解的。

归结复杂度；约束满足问题；可满足相变

A

TP301.5

10.3778/j.issn.1002-8331.1301-0137

SHEN Jing,MEI Dan.Resolution complexity of satisfiability instances.Computer Engineering and Applications, 2014,50（22）：69-72.

国家自然科学基金（No.11171370）。

沈静（1980—），女，博士，讲师，研究领域为人工智能；梅丹（1983—），女，硕士。E-mail：shendina@hotmail.com

2013-01-13

2013-02-25

1002-8331（2014）22-0069-04

CNKI网络优先出版：2013-03-19,http://www.cnki.net/kcms/detail/11.2127.TP.20130319.1424.009.html