A Review of Structural Characteristics of Satisfiability Problems

NAVIGATE

Table of Contents

STATISTICS

Viewed815

Downloads706

A Review of Structural Characteristics of Satisfiability Problems

[HTML] PDF下载 (706)

[1]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]

Copy

Journal of Zhengzhou University (Engineering Science)[ISSN 1671-6833/CN 41-1339/T] Volume: 44卷 Number of periods: 2023 06 Page number: 40-47 Column: Public date: 2023-12-25

Title:: A Review of Structural Characteristics of Satisfiability Problems

Author(s):: WANG Xiaofeng¹; 2; PANG Lichao¹; MO Chunhui¹; YANG Yi¹; ZHAO Xingyu¹; YANG Lan¹; 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

Keywords:: satisfiability problems; phase transition; tree decomposition; structural entropy; DNA origami

CLC:: TP301

DOI:: 10.13705/j.issn.1671-6833.2023.03.013

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.

Similar References:

Memo

Last Update: 2023-10-22