随机可满足实例集上警示传播算法的收敛性

信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公式因子图上圈存在的相变点.在随机kCNF公式产生模型G(n,k,p)中,取k=3,p=d/n2,因子图中圈存在的相变点为p=1/8n2.当d＜1/8时,因子图中开始出现圈,且每个连通分支至多有一个圈,因子图中含圈的连通分支的数目以及圈的长度均与n无关.因此,因子图是由森林和一些含有唯一圈的连通分支构成.证明了WP算法在这些实例集上高概率收敛,并且给出了算法的迭代步数为O(logn+s),其中,s为连通分支的大小.

Convergence of Warning Propagation Algorithms for Random Satisfiable Instances

Message propagation algorithms are very effective in finding satisfying assignments for random kSAT instances and hard regions become more narrow. Unfortunately, this phenomenon is still lacks rigorous theoretical proofs. The Warning Propagation (WP) algorithm is the most basic message propagation algorithm. In order to analysis the WP algorithm convergence for random kCNF formulas, the study gives the sharp threshold point for the existence of cycles in the factor graph of random kCNF formulas, the threshold for the existence of cycles in model G(n,k,p) of random kCNF formulas is p=1/8n² for k=3, p=d/n². When d becomes asymptotically equal to 1/8, cycles begin to appear, but each component contains at most one cycle, the number of the components containing a single cycle and the length of cycle are a constant independent of n. Thus, the factor graph consists of a forest of trees plus a few components that have a single cycle. Then WHP (with high probability) after at most O(logn+s) iterations, WP converges on these instances. Here s is the size of the connected component.