随机正则恰当(d,k)-SAT问题的可满足相变分析  

Satisfiable phase transition in random regular exact(d,k)-SAT problem

作　　者：王晓峰[1,2] 王军霞 WANG Xiaofeng;WANG Junxia(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;Key Laboratory of Images and Graphics Intelligent Processing of the National Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021 [2]北方民族大学图像图形智能处理国家民委重点实验室,宁夏银川750021

出　　处：《华中科技大学学报（自然科学版）》2024年第11期85-92,共8页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(62062001);宁夏青年拔尖人才培养项目(2021)。

摘　　要：为深入理解随机正则恰当(d,k)-SAT问题难解的内在本质,理清相变与难解之间的变化规律,进一步设计高效的求解算法,引入随机正则恰当可满足性实例产生模型,采用一阶矩和二阶矩方法分析了该问题的相变情况,给出了正则恰当(d,k)-SAT问题的可满足相变点d^(*).当相变控制参数d^(*)时,正则恰当(d,k)-SAT问题实例高概率可满足;当d>d^(*)时,正则恰当(d,k)-SAT问题实例高概率不可满足.最后,选取子句长度k分别为3和4进行实验,结果表明:在d^(*)的取值分别为2.3798和3.0668附近发生了相变现象,进一步证明了理论结果与实验结果的一致性.To gain a deeper understanding of the inherent nature of the difficulty in solving the random regular exact(d,k)-SAT problem,clarify the changing patterns between phase transitions and difficulty,and further design efficient solving algorithms.A random regular exact satisfiability instance generation model was introduced,and the phase transition of the problem was analyzed using first moment and second moment methods.The satisfiability phase transition point d^(*)for the random regular exact(d,k)-SAT problem was given.When the phase transitions control parameter d<d^(*),the random regular exact(d,k)-SAT problem instance had a high probability of being satisfied.When d>d^(*),the random regular exact(d,k)-SAT problem instances had a high probability of not being satisfied.Finally,experiments were conducted with clause lengths k of 3 and 4,respectively.Results show that the phase transitions occur around d^(*)values of 2.3798 and 3.0668,which further confirms the consistency between theoretical and experimental results.

关 键 词：随机正则恰当(d k)-SAT问题 一阶矩 二阶矩 可满足性问题 相变分析 

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