Survey Propagation: An Effective Algorithm for Solving SAT
Shao Li · 2005
The Survey propagation is a new SAT(CSP)algorithm. It is a spin glass model based on statistic physics, which makes survey for specific problems, so as to greatly reduce the complexity of solving. But the sp aigorithm sometime is conrergence,or leads to erroneous solutions. For this reason,in this paper,a simple backtraking is induct- ed into SP,thereby partialy solves this kind of SAT problems.