                                               Convergence of Warning Propagation Algorithms for Random Satisfiable Instances

DOI：10.3724/SP.J.1001.2013.04213

 作者 单位 E-mail 王晓峰 贵州大学 计算机科学系,贵州 贵阳 550025 许道云 贵州大学 计算机科学系,贵州 贵阳 550025 dyxu@gzu.edu.cn 韦立 贵州大学 计算机科学系,贵州 贵阳 550025

信息传播算法在求解随机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为连通分支的大小.

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/8n2 for k=3, p=d/n2. 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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器     主办单位：中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4 编辑部电话：+86-10-62562563 E-mail: jos@iscas.ac.cn Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved 本刊全文数据库版权所有，未经许可，不得转载，本刊保留追究法律责任的权利 