随机k-SAT的相变上下界

作者：李倩倩; 王以松; 冯仁艳; 张振鹏

来源：贵州大学学报(自然科学版), 2016, 33(05): 86-90.

DOI：10.15958/j.cnki.gdxbzrb.2016.05.18

• k-SAT
• 可满足性
• 相变
• 阈值

在随机k-SAT模型的基础上,针对合取范式的满足性问题进行研究。对于固定的变量数n,随着子句数m增加,当m/n接近某一值时公式的可满足性发生剧烈的变化,可满足的概率从1变为0,也就是经常提到的相变问题。证明k-SAT相变的阈值上界为2kln2;当k(k<53)比较小时阈值下界为2k-1ln2;当k(k≥53)比较大的时候,对任何ε=ε(k)>0(ε是关于k的函数)且εn→!(趋近无穷大),存在α0=2k ln2,使得下界为αl=(1-ε)α0。通过实验对k为2,3,4时的阈值进行验证。

• 单位
  贵州大学