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

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

为深入理解均衡正则恰当(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.