WP可解公式上警示传播算法收敛的有效条件

Effective conditions for warning propagation algorithm convergence on WP solvable formula

通过对警示传播(warning propagation,WP)算法的数学原理分析,高概率确定的部分变元与公式的骨干集和后门集有密切关系。针对WP算法收敛性的研究,基于骨干集和后门集定义WP-可解公式,利用在G(n,3,m)模型和植入指派模型下证明WP算法的收敛性,给出算法收敛的充要条件。最后,通过在植入指派的公式产生模型上进行数值实验验证,结果表明:如果一个可满足性公式WP-可解公式,当且仅当WP算法高概率收敛。

Through the analysis of the mathematical principle of WP algorithm,it could be found that the partial variables determined by high probability are closely related to the backbone set and backdoor set of the formula.For the study of the convergence of WP-solvable formula and WP algorithm,this paper defined WP-solvable formula based on backbone set and backdoor set,and proved the convergence of the WP algorithm by using the G(n,3,m)model and the planted distribution model,it gave the necessary and sufficient conditions for the convergence of the algorithm.Finally,it carried out the numerical experiments on the model of the planted distribution formula.The results show that if a satisfiability formula WP-solvable formula,if and only if the WP algorithm has a high probability of convergence.