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

Satisfiability threshold of regular(k,r)-SAT problem via 1RSB theory

作　　者：周锦程 许道云[2] 卢友军[2] Zhou Jincheng;Xu Daoyun;Lu Youjun(School of Mathematics and Statistics, Qiannan Normal University for Nationalities, Duyun 558000, Guizhou China;College of Computer Science and Technology, Guizhou University, Guiyang 550025, China)

机构地区：[1]黔南民族师范学院数学与统计学院,贵州都匀558000 [2]贵州大学计算机科学与技术学院,贵州贵阳550025

出　　处：《华中科技大学学报（自然科学版）》2017年第12期7-13,共7页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(61762019;61463044;61462001);贵州省科技厅联合基金资助项目(LKQS201313;LKQS201314);中央财政专项课题资助项目(2014ZCSX13);黔南州工业科技计划资助项目[黔南科合工字(2017)10号]

摘　　要：针对每个变元恰好出现r次且其正、负出现各为r/2次的随机正则(k,r)-SAT问题,结合一阶复本对称破缺理论和随机正则(k,r)-CNF公式解空间的几何结构,分析了通常以解的总数作为一阶矩方法的随机变量时,所得到的随机正则(k,r)-SAT问题可满足临界值上界偏大的本质原因.在此基础上,通过计算可满足相变点附近区域中随机正则(k,r)-CNF公式的解的聚类总数,从而把计算其解的规模转换为计算其解的聚类规模.进一步,通过引入覆盖的定义来表示聚类,并以覆盖总数作为一阶矩方法中的随机变量,结合相关的概率分析,得到了当前该问题可满足临界值点的一个新上界,使得上、下界之间仅有常数1的间隙.For the strictly regular（k,r）-SAT problem where each variables occurs precisely r times and each of the positive and negative literals occurs precisely r/2 times,combined with the one step replica symmetry breaking ansatz theory and the geometric structure of the solution space for the regular random（k,r）-CNF formulas,the fundamental reason why the upper bound be slightly larger when selecting random variable as the total number of satisfying assignments for regular random（k,r）-CNF formula in the first moment method was in-depth analyzed.On this basis,the total cluster number of the solutions at the critical region near the phase transition point was just calculated.Thus,the calculating of the number of the solutions was converted into the calculating of the number of the clusters.By introducing the concept of cover to represent a cluster,and using the total number of covers as the random variables in the first moment method,through some relevant probability analysis,a new upper bound of the phase transformation point for the regular random（k,r）-SAT problem can be obtained and there is only a constant 1 gap between the upper and lower bound.

关 键 词：随机正则(k r)-SAT问题 相变性质 1RSB腔域方法 可满足临界 变元 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]