Computer Science ›› 2018, Vol. 45 ›› Issue (11): 312-317.doi: 10.11896/j.issn.1002-137X.2018.11.050

• Interdiscipline & Frontier • Previous Articles    

Modified Warning Propagation Algorithm for Solving Regular (3,4)-SAT Instance Sets

SHE Guang-wei, XU Dao-yun   

  1. (College of Computer Science and Technology,Guizhou University,Guiyang 550025,China)
  • Received:2018-07-12 Published:2019-02-25

Abstract: Based on the critical characterization of the minimal unsatisfiable formula,a 3-CNF formula can be reduced to a regular (3,4)-CNF formula within polynomial time.Thus the regular (3,4)-SAT problem is NP-complete.The war-ning propagation algorithm(WP) converges in high probability on the regular (3,4)-SAT instance sets by reducing,but it can’t determine the satisfiability of the formula on any instance,so the algorithm fails to solve the problem.For a reduced regular (3,4)-CNF formula,the difference between the positive and negative occurences of each variable has been found to be stable.With this feature,a WP algorithm based on the rule of positive and negative occurences was proposed to solve the reduced regular (3,4)-SAT instances.The experimental results show that the modified WP algorithm is effective for regular formulas.Therefore,the regularity of the formula can be used to study the convergence of the WP algorithm.

Key words: 4)-SAT problem, Minimal unsatisfiable formula, Regular (3, Warning propagation algorithm

CLC Number: 

  • TP301
[1]ASPVALL B,PLASS M F,TARJAN R E.A linear-time algorithm for testing the truth of certain quantified boolean formulas[J].Information Processing Letters,1979,8(3):121-123.
[2]COOK S A.The complexity of theorem-proving procedures[C]∥ Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing (STOC’71).1971:151-158.
[3]CRAWFORD J M,ANTON L D.Experimental results on the crossover point in satisfiability problems[C]∥Proceedings of the 11th National Conference on Artificial Intelligence (AAAI-93).Washington,DC,USA,1993:21-27.
[4]KIRKPATRICK S,SELMAN B.Critical behavior in the satisfia- bility of random boolean expressions[J].Science,1994,264(5163):1297-1301.
[5]FRIEDGUT E,BOURGAIN J.Sharp thresholds of graph pro- perties,and the k-sat problem[J].Journal of the American Mathe-matical Society,1999,12(4):1017-1055.
[6]MÈZARD M,PARISI G.The Cavity Method at Zero Temperature[J].Journal of Statistical Physics,2003,111(1-2):1-34.
[7]MÈZARD M,PARISI G,ZECCHINA R.Analytic and algorithmic solution of random satisfiability problems[J].Science,2002,297(5582):812-815.
[8]BRAUNSTEIN A,MÈZARD M,ZECCHINA R.Survey propagation:An algorithm for satisfiability[J].Random Structures and Algorithms,2005,27(2):201-226.
[9]FEIGE U,MOSSEL E,VILENCHIK D.Complete convergence of message passing algorithms for some satisfiability problems[C]∥Proceedings of Random06.2008:339-350.
[10]WANG X F,XU D Y,WEI L.Convergence of Warning Propagation Algorithms for Random Satisfiable Instances[J].Journal of Software,2013,24(1):1-11.(in Chinese)
王晓峰,许道云,韦立.随机可满足实例集上警示传播算法的收敛性[J].软件学报,2013,24(1):1-11.
[11]WANG X F,XU D Y.Sufficient Conditions for Convergence of the Warning Propagation Algorithm[J].Journal of Software,2016,27(12):3003-3013.(in Chinese)
王晓峰,许道云.警示传播算法收敛的充分条件[J].软件学报,2016,27(12):3003-3013.
[12]XU D Y.Applications of minimal unsatisfiable formulas to polynomially reduction for formulas[J].Journal of Software,2006,17(5):1204-1212.(in Chinese)
许道云.极小不可满足公式在多项式归约中的应用[J].软件学报,2006,17(5):1204-1212.
[13]XU D Y,WANG X F.A Regular NP-Complete Problem and Its Inapproximability[J].Journal of Frontiers of Computer Science &Technology,2013,7(8):691-697.(in Chinese)
许道云,王晓峰.一个正则NP-完全问题及其不可近似性[J].计算机科学与探索,2013,7(8):691-697.
[14]WANG X F,QIANG L I,DING H S.Convergence of Warning Propagation Algorithm for Regular Structure Instances[J].Computer Science,2015,42(1):279-284.(in Chinese)
王晓峰,李强,丁红胜.规则实例集上警示传播算法的收敛性[J].计算机科学,2015,42(1):279-284.
[1] HE Bin, XU Dao-yun. Community Structure of Regular (3,4)-CNF Formula [J]. Computer Science, 2021, 48(4): 26-30.
[2] WANG Xiao-feng, LI Qiang and DING Hong-sheng. Convergence of Warning Propagation Algorithm for Regular Structure Instances [J]. Computer Science, 2015, 42(1): 279-284.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!