{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:28:31Z","timestamp":1760236111382,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2021,10,22]],"date-time":"2021-10-22T00:00:00Z","timestamp":1634860800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62062001, 61762019, 61862051, 61962002"],"award-info":[{"award-number":["62062001, 61762019, 61862051, 61962002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Major Scientific Research Projects of North Minzu University","award":["ZDZX201901"],"award-info":[{"award-number":["ZDZX201901"]}]},{"name":"Natural Science Foundation of Ningxia Province of China","award":["2020AAC03214, 2020AAC03219, 2019AAC03119, 2019AAC03120"],"award-info":[{"award-number":["2020AAC03214, 2020AAC03219, 2019AAC03119, 2019AAC03120"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Analyzing the solution space structure and evolution of 3-satisfiability (3-SAT) problem is an important way to study the difficulty of the solving satisfiability (SAT) problem. However, there is no unified analysis model for the spatial structure and evolution of solutions under different constraint densities. The analysis of different phase transition points and solution regions is based on different metric analysis models. The solution space of 3-SAT problem is obtained by planting strategy and belief propagation. According to the distribution of the influence of frozen variables on the solution, a label propagation algorithm based on planting strategy is proposed, is used to find the solution cluster, and then the structure entropy is used to measure its structure information. The structure entropy analysis model of 3-SAT problem solution space is established, and the unified analysis framework of solution space evolution and satisfiability phase transition is given. The experimental results show that the model is effective and can accurately analyze the evolution process of solution space and satisfiability phase transition, and verify the accuracy of interference phase transition point threshold predicted by long-range frustration theory.<\/jats:p>","DOI":"10.3390\/sym13112005","type":"journal-article","created":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T21:42:05Z","timestamp":1635198125000},"page":"2005","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0588-8673","authenticated-orcid":false,"given":"Chen","family":"Liang","sequence":"first","affiliation":[{"name":"College of Computer Science and Engineering, North Minzu University, Yinchuan 750021, China"}]},{"given":"Xiaofeng","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Computer Science and Engineering, North Minzu University, Yinchuan 750021, China"},{"name":"Ningxia Key Laboratory of Information and Big Data Processing, North Minzu University, Yinchuan 750021, China"}]},{"given":"Lei","family":"Lu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Engineering, North Minzu University, Yinchuan 750021, China"}]},{"given":"Pengfei","family":"Niu","sequence":"additional","affiliation":[{"name":"College of Computer Science and Engineering, North Minzu University, Yinchuan 750021, China"}]}],"member":"1968","published-online":{"date-parts":[[2021,10,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2085","DOI":"10.1016\/j.disc.2008.04.025","article-title":"The SAT\u2013UNSAT transition for random constraint satisfaction problems","volume":"309","author":"Creignou","year":"2009","journal-title":"Discret. Math."},{"key":"ref_2","first-page":"459","article-title":"Hard and easy distributions of SAT problems","volume":"92","author":"Mitchell","year":"1992","journal-title":"AAAI"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0304-3975(01)00149-9","article-title":"Statistical mechanics methods and phase transitions in optimization problems","volume":"265","author":"Martin","year":"2001","journal-title":"Theor. Comput. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","article-title":"Critical Behavior in the Satisfiability of Random Boolean Expressions","volume":"264","author":"Kirkpatrick","year":"1994","journal-title":"Science"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1126\/science.1073287","article-title":"Analytic and Algorithmic Solution of Random Satisfiability Problems","volume":"297","author":"Mezard","year":"2002","journal-title":"Science"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1002\/rsa.20090","article-title":"Threshold values of random K-SAT from the cavity method","volume":"28","author":"Mertens","year":"2005","journal-title":"Random Struct. Algorithms"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"10318","DOI":"10.1073\/pnas.0703685104","article-title":"Gibbs states and the set of solutions of random constraint satisfaction problems","volume":"104","author":"Krzakala","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"P04004","DOI":"10.1088\/1742-5468\/2008\/04\/P04004","article-title":"Clusters of solutions and replica symmetry breaking in random k-satisfiability","volume":"2008","author":"Montanari","year":"2008","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"066102","DOI":"10.1103\/PhysRevE.77.066102","article-title":"T\u21920 mean-field population dynamics approach for the random3-satisfiability problem","volume":"77","author":"Zhou","year":"2008","journal-title":"Phys. Rev. E"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/PL00011099","article-title":"The Bethe lattice spin glass revisited","volume":"20","author":"Parisi","year":"2001","journal-title":"Eur. Phys. J. B-Condens. Matter Complex Syst."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1317","DOI":"10.1007\/s10955-006-9162-3","article-title":"Reconstruction on Trees and Spin Glass Transition","volume":"124","author":"Montanari","year":"2006","journal-title":"J. Stat. Phys."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"217203","DOI":"10.1103\/PhysRevLett.94.217203","article-title":"Long-Range Frustration in a Spin-Glass Model of the Vertex-Cover Problem","volume":"94","author":"Zhou","year":"2005","journal-title":"Phys. Rev. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1088\/1367-2630\/7\/1\/123","article-title":"Long-range frustration in finite connectivity spin glasses: A mean-field theory and its application to the randomK-satisfiability problem","volume":"7","author":"Zhou","year":"2005","journal-title":"New J. Phys."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3290","DOI":"10.1109\/TIT.2016.2555904","article-title":"Structural Information and Dynamical Complexity of Networks","volume":"62","author":"Li","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.physa.2016.09.009","article-title":"Resistance maximization principle for defending networks against virus attack","volume":"466","author":"Li","year":"2017","journal-title":"Phys. A Stat. Mech. its Appl."},{"key":"ref_16","first-page":"1","article-title":"Decoding topologically associating domains with ultra-low resolution Hi-C data by graph structural entropy","volume":"9","author":"Li","year":"2018","journal-title":"Nat. Commun."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"20412","DOI":"10.1038\/srep20412","article-title":"Three-Dimensional Gene Map of Cancer Cell Types: Structural Entropy Minimisation Principle for Defining Tumour Subtypes","volume":"6","author":"Li","year":"2016","journal-title":"Sci. Rep."},{"key":"ref_18","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computer and Intractability\u2014A Guide to the Theory of NP-Completeness, Freeman and Company."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1109\/18.910572","article-title":"Factor graphs and the sum-product algorithm","volume":"47","author":"Kschischang","year":"2001","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.20057","article-title":"Survey propagation: An algorithm for satisfiability","volume":"27","author":"Braunstein","year":"2005","journal-title":"Random Struct. Algorithms"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"285003","DOI":"10.1088\/1751-8113\/43\/28\/285003","article-title":"Belief propagation for graph partitioning","volume":"43","year":"2010","journal-title":"J. Phys. A Math. Theor."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"P11016","DOI":"10.1088\/1742-5468\/2005\/11\/P11016","article-title":"Survey-propagation decimation through distributed local computations","volume":"2005","author":"Chavas","year":"2005","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"031102","DOI":"10.1103\/PhysRevE.79.031102","article-title":"From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy","volume":"79","author":"Li","year":"2009","journal-title":"Phys. Rev. E"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"012011","DOI":"10.1088\/1742-6596\/233\/1\/012011","article-title":"Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations","volume":"233","author":"Zhou","year":"2010","journal-title":"Phys. Conf. Ser."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"066108","DOI":"10.1103\/PhysRevE.80.066108","article-title":"Communities of solutions in single solution clusters of a randomK-satisfiability formula","volume":"80","author":"Zhou","year":"2009","journal-title":"Phys. Rev. E"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/11\/2005\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:21:45Z","timestamp":1760167305000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/11\/2005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,22]]},"references-count":25,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["sym13112005"],"URL":"https:\/\/doi.org\/10.3390\/sym13112005","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2021,10,22]]}}}