随机均衡正则恰当(2s,k)-SAT问题的可满足相变  

Phase transition of in random balance regular exact(2s,k)-SAT problem

作　　者：王晓峰[1,2,3] 于卓 周锦程 许道云[3] WANG Xiaofeng;YU Zhuo;ZHOU Jincheng;XU Daoyun(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;The Key Laboratory of Images&Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China;School of Computer Science and Technology,Guizhou University,Guiyang 550025,China;School of Mathematics and Statistics,Qiannan Normal University for Nationalities,Duyun 558000,Guizhou China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021 [2]北方民族大学图像图形智能处理国家民委重点实验室,宁夏银川750021 [3]贵州大学计算机科学与技术学院,贵州贵阳550025 [4]黔南民族师范学院数学与统计学院,贵州都匀558000

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

基　　金：国家自然科学基金资助项目(62062001,61762019,61862051,61962002);宁夏自然科学基金资助项目(2020AAC03214,2020AAC03219);北方民族大学重大专项资助项目(ZDZX201901).

摘　　要：为深入理解均衡正则恰当(2s,k)-SAT问题的判定难度和可满足性解的分布情况,引入随机实例产生模型,利用一阶矩和二阶矩方法分析可满足性相变现象,给出随机均衡正则恰当(2s,k)-SAT问题可满足的相变点s∗.当s<s∗时,随机均衡正则恰当(2s,k)-SAT实例高概率可满足;当s>s∗时,随机均衡正则恰当(2s,k)-SAT实例高概率不可满足.最后,选取了k=4和k=6的两组数据集进行实验验证,结果表明理论结果与实验结果符合.To understand the difficulty of determining the equilibrium regular exact(2s,k)-SAT problem and the distribution of satisfiability solutions,a random instance generation model was introduced to analyze the satisfiability phase transition phenomenon using first moment and second moment methods.Set s∗is a threshold,it can be show that F of the stochastic balance regular exact(2s,k)-SAT problem instance is satisfiable with high probability if s<s∗and unsatisfiable with high probability if s>s∗.Finally,two sets of data sets with k=4 and k=6 were selected for experimental verification,and the results show that the theoretical results are consistent with the experimental results.

关 键 词：均衡正则恰当(2s k)-SAT问题 相变分析 可满足性问题 一阶矩 二阶矩 

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