Computer Science ›› 2018, Vol. 45 ›› Issue (11): 312-317.doi: 10.11896/j.issn.1002-137X.2018.11.050
• Interdiscipline & Frontier • Previous Articles
SHE Guang-wei, XU Dao-yun
CLC Number:
[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. |
|