可满足实例的归结复杂度

计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (22): 69-72.

可满足实例的归结复杂度

沈静，梅丹

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

出版日期:2014-11-15 发布日期:2014-11-13

Resolution complexity of satisfiability instances

SHEN Jing, MEI Dan

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

Online:2014-11-15 Published:2014-11-13

摘要/Abstract

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

关键词: 归结复杂度, 约束满足问题, 可满足相变

Abstract: 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.

Key words: resolution complexity, constraint satisfaction problem（CSP）, solubility phase transition

沈静，梅丹. 可满足实例的归结复杂度[J]. 计算机工程与应用, 2014, 50(22): 69-72.

SHEN Jing, MEI Dan. Resolution complexity of satisfiability instances[J]. Computer Engineering and Applications, 2014, 50(22): 69-72.

[1]	肖成龙，聂紫阳，王珊珊. 基于ParetoHeu和实例化失败统计的关联启发式方法[J]. 计算机工程与应用, 2020, 56(5): 57-64.
[2]	崔文正. RCC8的一致分割及其算法[J]. 计算机工程与应用, 2015, 51(1): 143-150.
[3]	朱臻1，高永明2，王斌2. 灵活准则地面测控资源约束满足模型研究[J]. 计算机工程与应用, 2014, 50(10): 260-265.
[4]	袁际军1，黄敏镁2. 基于UML与CCSP的产品配置方法[J]. 计算机工程与应用, 2013, 49(14): 1-9.
[5]	付宏杰^1，2，3，欧阳丹彤^1，2，孙吉贵^1，2. 一种求解二元约束满足问题自适应粒子群算法[J]. 计算机工程与应用, 2009, 45(29): 10-13.
[6]	侯睿. 结合方向关系和拓扑关系的约束满足推理[J]. 计算机工程与应用, 2008, 44(16): 63-65.
[7]	郭冬芬李铁克. 约束满足技术在热轧调度板坯排序中的应用[J]. 计算机工程与应用, 2007, 43(9期): 1-3.