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

作     者：王晓峰 于卓 周锦程 许道云 WANG Xiaofeng;YU Zhuo;ZHOU Jincheng;XU Daoyun

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

出 版 物：《华中科技大学学报（自然科学版）》 (Journal of Huazhong University of Science and Technology(Natural Science Edition))

年 卷 期：2022年第50卷第2期

页      面：105-111页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

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

摘      要：为深入理解均衡正则恰当(2s,k)-SAT问题的判定难度和可满足性解的分布情况,引入随机实例产生模型,利用一阶矩和二阶矩方法分析可满足性相变现象,给出随机均衡正则恰当(2s,k)-SAT问题可满足的相变点s∗.当ss∗时,随机均衡正则恰当(2s,k)-SAT实例高概率不可满足.最后,选取了k=4和k=6的两组数据集进行实验验证,结果表明理论结果与实验结果符合.