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

作者：王晓峰; 于卓; 周锦程; 许道云

来源：华中科技大学学报(自然科学版)科技大学, 2022, 50(02): 105-111.

DOI：10.13245/j.hust.220216

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

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

• 单位
  贵州大学; 黔南民族师范学院; 北方民族大学