计算机工程与应用Issue(22)：69-72,4.DOI:10.3778/j.issn.1002-8331.1301-0137
可满足实例的归结复杂度
Resolution complexity of satisfiability instances
摘要
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,(22):69-72,4.基金项目
国家自然科学基金（No.11171370）。 （）
