基于1 RSB的正则(k,r)-SA T问题可满足临界

• 作者: 卢友军 周锦程 许道云
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 工学
• 关键词: 随机正则(k,r)-SAT问题 相变性质 1RSB腔域方法 可满足临界 变元
• 年，卷（期）: 2017,（12）
• 所属期刊栏目: 计算机科学与技术
• 页码范围: 7-13
• 页数: 7页
• 分类号: TP301
• 字数: 8455字
• 语种: 中文
• DOI: 10.13245/j.hust.171202

摘要

针对每个变元恰好出现r次且其正、负出现各为r/2次的随机正则(k,r)-SAT问题,结合一阶复本对称破缺理论和随机正则(k,r)-CNF公式解空间的几何结构,分析了通常以解的总数作为一阶矩方法的随机变量时,所得到的随机正则(k,r)-SAT问题可满足临界值上界偏大的本质原因.在此基础上,通过计算可满足相变点附近区域中随机正则(k,r)-CNF公式的解的聚类总数,从而把计算其解的规模转换为计算其解的聚类规模.进一步,通过引入覆盖的定义来表示聚类,并以覆盖总数作为一阶矩方法中的随机变量,结合相关的概率分析,得到了当前该问题可满足临界值点的一个新上界,使得上、下界之间仅有常数1的间隙.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学与技术学院	125	460	12.0	16.0
2	卢友军	贵州大学计算机科学与技术学院	6	10	2.0	3.0