[1]王晓峰,庞立超,莫淳惠,等.可满足性问题的结构特征进展综述[J].郑州大学学报(工学版),2023,44(06):40-47.[doi:10.13705/j.issn.1671-6833.2023.03.013]
　WANG Xiaofeng,PANG Lichao,MO Chunhui,et al.A Review of Structural Characteristics of Satisfiability Problems[J].Journal of Zhengzhou University (Engineering Science),2023,44(06):40-47.[doi:10.13705/j.issn.1671-6833.2023.03.013]
点击复制

可满足性问题的结构特征进展综述()
分享到：

《郑州大学学报(工学版)》[ISSN:1671-6833/CN:41-1339/T]

卷:
44
期数:
2023年06期
页码:
40-47
栏目:
出版日期:
2023-12-25

文章信息/Info

Title:
A Review of Structural Characteristics of Satisfiability Problems
作者:
王晓峰1; 2;  庞立超1;  莫淳惠1;  杨 易1;  赵星宇1;  杨 澜1
1. 北方民族大学 计算机科学与工程学院,宁夏 银川 750021;2. 北方民族大学 图像图形智能处理国家民委重点实 验室 宁夏,银川 750021
Author(s):
WANG Xiaofeng1; 2;  PANG Lichao1;  MO Chunhui1;  YANG Yi1;  ZHAO Xingyu1;  YANG Lan1
1. School of Computer Science and Engineering, North Minzu University, YinChuan 750021,China; 2. Key Laboratory of Image and Graphics Intelligent Processing of State Ethnic Affairs Commission, North Minzu University, YinChuan 750021,China
关键词:
SAT 问题;  相变;  树分解;  结构熵;  DNA 折纸术
Keywords:
satisfiability problems;  phase transition;  tree decomposition;  structural entropy;  DNA origami
分类号:
TP301
DOI:
10.13705/j.issn.1671-6833.2023.03.013
文献标志码:
A
摘要:
可满足性( SAT)问题是人工智能的基础问题,也是 NP 难问题,在机器学习、模式识别和自然语言处理等领 域有着实际应用。 然而,随着人工智能发展,越来越多的问题呈现出更为复杂的形态,原有的算法不再适用,需进 一步优化或者改进,这对基础研究提出了更高要求。 为了研究 SAT 问题难解的内在本质,需要研究其结构特征,进 而找出求解 SAT 问题的高效算法。 近年来备受研究人员关注的相变、树宽、结构熵、DNA 折纸术是 SAT 问题结构 特征的 4 种常用度量模型。 为了理清关于 SAT 问题结构特征的研究进展,基于上述 4 种度量模型,对 SAT 问题的 结构特征进行了综述,指出了 SAT 问题结构特征研究所面临的挑战及未来的方向。 在 SAT 问题求解中相变分析、 树分解算法、结构熵及 DNA 折纸术等方面虽已取得一定的研究成果,但在相变点精确上界的求解、结构度量模型 指导 SAT 求解器设计,以及树分解算法效率的提高等方面仍待突破,这将成为未来关于 SAT 问题结构特征研究的 重点。
Abstract:
Satisfiability ( SAT) problem is the basic problem of artificial intelligence, which is also a hard problem of NP. It has practical applications in machine learning, pattern recognition and natural language processing. However, with the development of artificial intelligence, more and more complex problems popped up. The original algorithms were no longer applicable and need to be further optimized or improved, which put forward higher requirements for basic research. In order to study the inherent nature of the difficult SAT problem, the structural characteristics of the problem were studied, and then the efficient algorithm to solve the SAT problem were found out. Phase transition, tree width, structural entropy, and DNA origami were four metric models for studying the structural characteristics of SAT problems, which attracted the attention of researchers in recent years. In order to clarify the research progress on the structural characteristics of SAT problems, based on the above four measurement models, the structural characteristics of SAT problems were summarized, and the challenges and future directions of the research on structural characteristics of SAT problems were pointed out. Although some research achievements were made in phase change analysis, tree decomposition algorithm, structural entropy and DNA origami in solving SAT problems, breakthroughs are still needed in solving the accurate upper bound of phase change points, guiding the design of SAT solvers by structural metric model, and improving the efficiency of tree decomposition algorithm, which will become the focus of future research on structural characteristics of SAT problems.

参考文献/References:

[1] DYER M, FRIEZE A, MOLLOY M. A probabilistic analysis of randomly generated binary constraint satisfaction problems[ J] . Theoretical Computer Science, 2003, 290(3) : 1815-1828. 

[2] VIZEL Y, WEISSENBACHER G, MALIK S. Boolean satisfiability solvers and their applications in model checking[ J] . Proceedings of the IEEE, 2015, 103 ( 11 ) : 2021-2035. 
[3] DAVIS M, PUTNAM H. A computing procedure for quantification theory[ J] . Journal of the ACM, 1960, 7 (3) : 201-215.
 [4] ZHAO C Y, ZHOU H J, ZHENG Z M, et al. A message-passing approach to random constraint satisfaction problems with growing domains[ J] . Journal of Statistical Mechanics: Theory and Experiment, 2011, 2011 ( 2 ): P02019.
 [5] WANG H F, FAN H, LI F L. Quantum algorithm for solving some discrete mathematical problems by probing their energy spectra[J]. Physical Review A, 2014, 89: 012306.
 [6] 莫孝玲, 许道云. CNF 公式赋值空间上可满足解的概 率性质[ J] . 计算机科学与探索, 2018, 12(11) : 1852 -1861. MO X L, XU D Y. Probabilistic properties of satisfiable solutions on space of assignments for CNF formula [ J] . Journal of Frontiers of Computer Science and Technology, 2018, 12(11) : 1852-1861.
 [7] ACHLIOPTAS D, COJA-OGHLAN A, RICCI-TERSENGHI F. On the solution-space geometry of random constraint satisfaction problems [ J ] . Random Structures & Algorithms, 2011, 38(3) : 251-268. 
[8] MEZARD M, RICCI-TERSENGHI F, ZECCHINA R. Two solutions to diluted p-spin models and XORSAT problems[ J] . Journal of Statistical Physics, 2003, 111 (3) : 505-533.
 [9] MANEVA E, SINCLAIR A. On the satisfiability threshold and clustering of solutions of random 3-SAT formulas [ J ] . Theoretical Computer Science, 2008, 407 ( 1 / 2 / 3) : 359-369. 
[10] MITZENMACHER M, UPFAL E. 概率与计算[ M] . 冉 启康等译. 北京: 机械工业出版社,2020. 
MITZENMACHER M, UPFAL E. Probability and computing[M] . RAN Q K, et al. Translated. Beijing: China Machine Press, 2020. 
[11] HARDY G H, LITTLEWOOD J E, PÓLYA G. Inequalities: a mathematical olympiad approach[M]. Cambridge: Cambridge University Press, 1952.
 [12] COJA-OGLAN A, PANAGIOTOU K. Catching the kNAESAT threshold[ C]∥Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing. New York: ACM, 2012: 899-908.
 [13] BOUFKHAD Y, DUBOIS O, INTERIAN Y, et al. Regular random k-SAT: properties of balanced formulas [ J] . Journal of Automated Reasoning, 2005, 35(1): 181-200. 
[14] DING J, SLY A, SUN N K. Satisfiability threshold for random regular NAE-SAT[ J] . Communications in Mathematical Physics, 2016, 341(2) : 435-489. 
[15] 张明明, 许道云. 正则 3-SAT 问题的相变现象[ J] . 计 算机科学, 2016, 43(4) : 33-36. 
ZHANG M M, XU D Y. Phase transition phenomenon of regular 3-SAT problem[ J] . Computer Science, 2016, 43 (4) : 33-36. 
[16] 周锦程, 许道云, 卢友军. 随机正则(k,r)-SAT 问题的可 满足临界[J]. 软件学报, 2016, 27(12): 2985-2993. 
ZHOU J C, XU D Y, LU Y J. Satisfiability threshold of the regular random ( k, r) -SAT problem [ J ] . Journal of Software, 2016, 27(12) : 2985-2993. 
[17] 王永平, 许道云. 取定 s 的严格 d-正则随机( 3, 2s) - SAT 问题的可满足临界[ J] . 软件学报, 2021, 32(9) : 2629-2641.
 WANG Y P, XU D Y. Satisfiability threshold of strictly d-regular random ( 3, 2s ) -SAT problem for fixed s [ J ] . Journal of Software, 2021, 32(9) : 2629-2641.
 [18] 周锦程, 许道云, 卢友军. 基于 1RSB 的正则 ( k,r) - SAT 问题可满足临界[ J] . 华中科技大学学报(自然科 学版) , 2017, 45(12) : 7-13. 
ZHOU J C, XU D Y, LU Y J. Satisfiability threshold of regular( k,r) -SAT problem via 1RSB theory[ J] . Journal of Huazhong University of Science and Technology (Natural Science Edition) , 2017, 45(12) : 7-13.
[19] 聂国霞, 秦永彬, 许道云. 基于因子图求解( 3, 4 = ) - CNF 公式类下可满足问题[ J] . 计算机与数字工程, 2013, 41(5) : 686-689. 
NIE G X, QIN Y B, XU D Y. Based on the factor graph for solving satisfiability problem of (3, 4 = ) -CNF formula class[ J ] . Computer & Digital Engineering, 2013, 41 (5) : 686-689.
 [20] 刘纯. 基于聚类的 SAT 实例结构分析[ D] . 武汉: 华 中科技大学, 2015. 
LIU C. The structural analysis of SAT instance based on clustering[ D] . Wuhan: Huazhong University of Science and Technology, 2015. 
[21] BERTELE U, BRIOSCHI F. Nonserial dynamic programming[M] . New York: Academic Press, 1972. 
[22] ARNBORG S, CORNEIL D G, PROSKUROWSKI A. Complexity of finding embeddings in a k-tree[ J] . SIAM Journal on Algebraic Discrete Methods, 1987, 8 ( 2 ) : 277-284.
 [23] FELLOWS M R, LANGSTON M A. Nonconstructive tools for proving polynomial-time decidability [ J ] . Journal of the ACM, 1988, 35(3) : 727-739.
 [24] ENRIGHT J, MEEKS K. Deleting edges to restrict the size of an epidemic: a new application for treewidth[ J] . Algorithmica, 2018, 80(6) : 1857-1889. 
[25] 雷 莹. 树 分 解 算 法 在 可 满 足 性 问 题 中 的 应 用 研 究 [D] . 贵阳: 贵州大学, 2020.
 LEI Y. Tree decomposition algorithm and application for the SAT[D] . Guiyang: Guizhou University, 2020.
 [26] TARJAN R E, YANNAKAKIS M. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs [ J] . SIAM Journal on Computing, 1984, 13 ( 3) : 566 -579.
 [27] HELL P, KIRKPATRICK D G. Algorithms for degree constrained graph factors of minimum deficiency [ J ] . Journal of Algorithms, 1993, 14(1) : 115-138.
 [28] AMIR E. Approximation algorithms for treewidth[ J] . Algorithmica, 2010, 56(4) : 448-479.
 [29] ARNBORG S, PROSKUROWSKI A. Linear time algorithms for NP-hard problems restricted to partial k-trees [ J] . Discrete Applied Mathematics, 1989, 23 ( 1) : 11 -24.
 [30] KOSTER A M C A, VAN HOESEL S P M, KOLEN A W J. Solving partial constraint satisfaction problems with tree decomposition[ J] . Networks, 2002, 40(3) : 170-180.
 [31] ZHAO J Z, MALMBERG R L, CAI L M. Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition[ J] . Journal of Mathematical Biology, 2008, 56(1) : 145-159.
 [32] ADCOCK A B, SULLIVAN B D, MAHONEY M W. Tree decompositions and social graphs[ J] . Internet Mathematics, 2016, 12(5) : 315-361. 
[33] 谢志新, 王晓峰, 于卓, 等. 基于树宽的警示传播算 法收敛性分析[ J] . 计算机应用研究, 2022, 39( 10) : 3061-3064, 3077. 
XIE Z X, WANG X F, YU Z, et al. Convergence analysis of warning propagation algorithm based on tree width [ J ] . Application Research of Computers, 2022, 39 (10) : 3061-3064, 3077.
 [34] 程亚南, 王晓峰, 刘凇佐, 等. 一种求解旅行商问题 的信息传播算法[ J] . 郑州大学学报(理学版) , 2022, 54(3) : 52-58. 
CHENG Y N, WANG X F, LIU S Z, et al. An information propagation algorithm for solving traveling salesman problem[ J] . Journal of Zhengzhou University ( Natural Science Edition) , 2022, 54(3) : 52-58.
 [35] LI A S, PAN Y C. Structural information and dynamical complexity of networks[ J] . IEEE Transactions on Information Theory, 2016, 62(6) : 3290-3339.
 [36] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[ J] . Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2004, 69 (2) : 026113. 
[37] 成科扬, 荣兰, 蒋森林, 等. 基于深度学习的遥感图 像超分辨率重建方法综述[ J] . 郑州大学学报( 工学 版) , 2022, 43(5) : 8-16. 
CHENG K Y, RONG L, JIANG S L, et al. Overview of methods for remote sensing image super-resolution reconstruction based on deep learning [ J] . Journal of Zhengzhou University (Engineering Science) , 2022, 43(5) : 8 -16.
 [38] ROTTA R, NOACK A. Multilevel local search algorithms for modularity clustering[ J] . ACM Journal of Experimental Algorithmics, 2011, 16(2) :1-27.
 [39] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[ J] . Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10) : P10008.
 [40] BROOKS J F P. Three great challenges for half-centuryold computer science[ J] . Journal of the ACM, 2003, 50 (1) : 25-26. 
[41] LIU X C, FU L Y, WANG X B, et al. On the similarity between Von Neumann graph entropy and structural information: interpretation, computation, and applications [C]∥IEEE Transactions on Information Theory. Piscataway: IEEE, 2022: 2182-2202. 
[42] BRAUNSTEIN S L, GHOSH S, SEVERINI S. The Laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states[ J] . Annals of Combinatorics, 2006, 10(3) : 291-317. 
[43] ZHANG Z J, XU D Y, ZHOU J C. A structural entropy measurement principle of propositional formulas in conjunctive normal form[ J] . Entropy, 2021, 23(3) : 303. 
[44] 牛进, 王晓峰, 左逢源, 等. 基于二维结构熵的置信 传播算法收敛性分析[ J] . 计算机应用研究, 2021, 38 (7) : 2032-2036, 2043. 
NIU J, WANG X F, ZUO F Y, et al. Convergence analysis of belief propagation algorithm based on two-dimensional structural entropy [ J ] . Application Research of Computers, 2021, 38(7) : 2032-2036, 204.
 [45] ADLEMAN L M. Molecular computation of solutions tocombinatorial problems[ J] . Science, 1994,266( 5187) : 1021-1024.
 [46] LIPTON R J. Using DNA to solve NP-complete problems [ J] . Science. 1995,268:542-545.
 [47] SAKAMOTO K, GOUZU H, KOMIYA K, et al. Molecular computation by DNA hairp information[ J] . Science, 2000,288(5469) :1223-1226. 
[48] BRAICH R S, CHELYAPOV N, JOHNSON C, et al. Solution of a 20-variable 3-SAT problem on a DNA computer[ J] . Science, 2002, 296(5567) : 499-502.
 [49] 张凤月, 殷志祥, 许进. DNA 芯片在 0-1 规划问题中 的应 用 [ J] . 生 物 化 学 与 生 物 物 理 进 展, 2003, 30 (3) : 412-415. 
ZHANG F Y, YIN Z X, XU J. Application of DNA chip on 0-1 planning problem [ J ] . Progress in Biochemistry and Biophysics, 2003, 30(3) : 412-415.
 [50] 周康, 魏传佳, 刘朔, 等. 可满足性问题的闭环 DNA 算法[ J] . 华中 科 技 大 学 学 报 ( 自 然 科 学 版) , 2009, 37(7) : 75-78. 
ZHOU K, WEI C J, LIU S, et al. Closed circle DNA algorithm for SAT problem[ J] . Journal of Huazhong University of Science and Technology ( Nature Science Edition) , 2009, 37(7) : 75-78. 
[51] XIAO J H, XU J. The DNA computation model based on giant magnetoresistance for SAT problem [ J ] . Chinese Journal of Computers, 2014, 36(4) : 829-835.
 [52] 马莹, 殷志祥, 方欢. 可满足性问题生物芯片 DNA 算 法[ J ] . 计 算 机 应 用 研 究, 2017, 34 ( 8 ) : 2310 - 2311, 2367. 
MA Y, YIN Z X, FANG H. DNA computation model based on biochips for satisfiability problem[ J] . Application Research of Computers, 2017, 34 ( 8 ) : 2310 - 2311, 2367.
 [53] 陈哲. 基 于 DNA 计 算 的 可 满 足 性 问 题 的 模 型 研 究 [D] . 淮南: 安徽理工大学, 2020. 
CHEN Z. Research on the model of satisfiability based on DNA computing[D] . Huainan: Anhui University of Science & Technology, 2020. 
[54] 麻晶晶, 许进. 基于 DNA 折纸术求解图的顶点着色 问题的 方 法 [ J] . 电 子 与 信 息 学 报, 2021, 43 ( 6) : 1750-1755. 
MA J J, XU J. A method for the graph vertex coloring problem based on DNA origami[ J] . Journal of Electronics & Information Technology, 2021, 43 ( 6 ) : 1750 -1755.

相似文献/References:

[1]郭茶秀,刘树兰..铝泡沫和石墨泡沫强化石蜡相变传热的数值模拟[J].郑州大学学报(工学版),2012,33(03):87.[doi:10.3969/j.issn.1671-6833.2012.03.022]
　GUÃ Chaxiu,LIU Shulan.Numerical Simulation of Heat Transfer Enhancement of Paraffin Wax PhaseChange with Mmetal Foam and Graphite Foam[J].Journal of Zhengzhou University (Engineering Science),2012,33(06):87.[doi:10.3969/j.issn.1671-6833.2012.03.022]
[2]卢红霞,毛爱霞,郝好山,等.利用纳米铝和沉淀法制备纳米α-Al2O3粉体[J].郑州大学学报(工学版),2005,26(01):83.[doi:10.3969/j.issn.1671-6833.2005.01.021]
　Lu Hongxia,Mao Aixia,Hao Haoshan,et al.Nano α-Al2O3 powder was prepared by nano-aluminum and precipitation[J].Journal of Zhengzhou University (Engineering Science),2005,26(06):83.[doi:10.3969/j.issn.1671-6833.2005.01.021]

更新日期/Last Update: 2023-10-22