Convergence of Warning Propagation Algorithms for Random Satisfiable Instances
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    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.

    Reference
    Related
    Cited by
Get Citation

王晓峰,许道云,韦立.随机可满足实例集上警示传播算法的收敛性.软件学报,2013,24(1):1-11

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:November 26,2011
  • Revised:March 27,2012
  • Adopted:
  • Online: December 29,2012
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063