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 satisfiab ility formula WP-solvable formula, if and only if the WP algorithm has a high probability of convergence. [ABSTRACT FROM AUTHOR]