计算机科学 ›› 2018, Vol. 45 ›› Issue (11): 312-317.doi: 10.11896/j.issn.1002-137X.2018.11.050
• 交叉与前沿 • 上一篇
佘光伟, 许道云
SHE Guang-wei, XU Dao-yun
摘要: 利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全性的正则(3,4)-SAT问题。警示传播算法(Warning Propagation,WP)在归约转换后的正则(3,4)-SAT实例集上高概率收敛,但在任意一个实例上都无法判断公式的可满足性,因此算法求解失效。对于一个归约转换后的正则(3,4)-CNF公式,每一变元出现的正负次数之差具有趋于稳定的结构特征,基于该特征,提出基于变元正负出现次数规则的WP算法来求解归约转换后的正则(3,4)-SAT实例。实验结果表明,修正的WP算法对正则公式的可满足性判定有效,从而可以利用公式的正则性特征进一步研究WP算法的收敛性特征条件。
中图分类号:
[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] | 何彬, 许道云. 正则(3,4)-CNF公式的社区结构 Community Structure of Regular (3,4)-CNF Formula 计算机科学, 2021, 48(4): 26-30. https://doi.org/10.11896/jsjkx.201000178 |
[2] | 王晓峰,李强,丁红胜. 规则实例集上警示传播算法的收敛性 Convergence of Warning Propagation Algorithm for Regular Structure Instances 计算机科学, 2015, 42(1): 279-284. https://doi.org/10.11896/j.issn.1002-137X.2015.01.062 |
[3] | 秦永彬,许道云,王晓峰. 基于警示传播与DPLL算法的启发式极性决策算法 Heuristic Polarity Decision Making Algorithm Based on Warning Propagation and DPLL Algorithm 计算机科学, 2010, 37(12): 178-181. |
|