随机k-SAT的相变上下界

The Upper and Lower Bounds of Phase Transition for Random k-SAT

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

Based on the model of random k-SAT, the satisfiability problem of formulas in conjunctive normal form was studied. For fixed number of variables n , as the number of clause m increased, when m/n was close to a certain value , the satisfiability dramatically changes and its probability changes from 1 to 0, which is often mentioned phase transition. The paper proves that the upper bound of phase transition for random k-SAT is 2^k ln2, when k （ k 〈 53）is smaller, the lower bound is2^k-l ln2;when k （ k ≥ 53）is larger, for any ε = ε（k） 〉 0 （ ε function about k ） and εn→∞（ approaching infinity）, there exists α0 = 2^k ln2 making lower bound being α1 = （1 - ε）α0. These theoretical results have been verified by experimental data for k is 2,3,4 respectivelv.