Convergence Of Message Propagation Algorithms For Planted Distribution Instance

As a very important NP complete problem,the satisfiability(SAT)problem of propositional formula is closely related to many complex problems in the field of artificial intelligence,such as constraint solving,planning,and learning.With the development of artificial intelligence,the original solution algorithm of SAT problem needs to be reviewed and designed,so it provides new opportunities and challenges for studying SAT problem.In the eighties of the last century,physicists proposed an message propagation algorithm based on message passing.Using the message propagation algorithm to solve the SAT problem to obtain an approximate solution,the effect was significant.However,there are certain deficiencies in the analysis of the convergence of message propagation algorithms,which leads to insufficient understanding of the convergence of message propagation algorithms,and there is currently no systematic theoretical explanation for this situation.Based on the WP-solvable formula,this thesis conducts the research on the convergence of the research message propagation algorithm,and tries to explain it theoretically,main as follows:(1)By analyzing the principle of the message propagation algorithm,it is found that there is a certain relationship between the backbone set and the backdoor set under the message propagation algorithm.Based on this characteristic,the definition of the WP-solvable formula is given;(2)Based on the characteristics of the WP-solvable formula,the model of planted distribution instances is used to study the convergence of the message propagation algorithm on the WP-solvable formula.An effective condition for the convergence of the message propagation algorithm is given: the message propagation algorithm is on high probability convergence in formula F,if and only if formula F is a WP-solvable formula.This thesis gives the conditions for the convergence of the message propagation algorithm,which provides a certain theoretical basis for the wide application of the artificial intelligence field of the message propagation algorithm.