用于求解正则(3,4)-SAT实例集的修正警示传播算法

doi:10.11896／j.issn.1002-137X.2018.11.050

计算机科学 ›› 2018, Vol. 45 ›› Issue (11): 312-317.doi: 10.11896／j.issn.1002-137X.2018.11.050

• 交叉与前沿 • 上一篇

用于求解正则(3,4)-SAT实例集的修正警示传播算法

佘光伟, 许道云

(贵州大学计算机科学与技术学院贵阳550025)

收稿日期:2018-07-12 发布日期:2019-02-25
作者简介:佘光伟(1993-),男,硕士生,主要研究方向为算法设计与分析;许道云(1959-),男,教授,博士生导师,主要研究方向为可计算性与计算复杂性,E-mail:dyxu@gzu.edu.cn(通信作者)。
基金资助:
本文受国家自然科学基金项目(61762019,61462001)资助。

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

SHE Guang-wei, XU Dao-yun

(College of Computer Science and Technology,Guizhou University,Guiyang 550025,China)

Received:2018-07-12 Published:2019-02-25

摘要/Abstract

摘要： 利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全性的正则(3,4)-SAT问题。警示传播算法(Warning Propagation,WP)在归约转换后的正则(3,4)-SAT实例集上高概率收敛,但在任意一个实例上都无法判断公式的可满足性,因此算法求解失效。对于一个归约转换后的正则(3,4)-CNF公式,每一变元出现的正负次数之差具有趋于稳定的结构特征,基于该特征,提出基于变元正负出现次数规则的WP算法来求解归约转换后的正则(3,4)-SAT实例。实验结果表明,修正的WP算法对正则公式的可满足性判定有效,从而可以利用公式的正则性特征进一步研究WP算法的收敛性特征条件。

关键词: 4)-SAT问题, 极小不可满足公式, 警示传播算法, 正则(3

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

中图分类号:

TP301

佘光伟, 许道云. 用于求解正则(3,4)-SAT实例集的修正警示传播算法[J]. 计算机科学, 2018, 45(11): 312-317. https://doi.org/10.11896／j.issn.1002-137X.2018.11.050

SHE Guang-wei, XU Dao-yun. Modified Warning Propagation Algorithm for Solving Regular (3,4)-SAT Instance Sets[J]. Computer Science, 2018, 45(11): 312-317. https://doi.org/10.11896／j.issn.1002-137X.2018.11.050

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

用于求解正则(3,4)-SAT实例集的修正警示传播算法

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

Metrics

本文评价

推荐阅读 0

[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.