可满足实例的归结复杂度

• 作者: 梅丹 沈静
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 归结复杂度 约束满足问题 可满足相变
• 年，卷（期）: 2014,（22）
• 所属期刊栏目: 理论研究、研发设计
• 页码范围: 69-72
• 页数: 4页
• 分类号: TP301.5
• 字数: 4378字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1301-0137

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	沈静	海军工程大学应用数学系	23	73	4.0	7.0
2	梅丹	海军工程大学应用数学系	17	53	4.0	6.0