A New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy

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

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Chen Liang, Xiaofeng Wang, Lei Lu, Pengfei Niu
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	the satisfiability problem structure entropy belief propagation algorithm label propagation algorithm Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/c45b89cf20d5438aaaedca97b21cfa16
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:c45b89cf20d5438aaaedca97b21cfa16
record_format	dspace
spelling	oai:doaj.org-article:c45b89cf20d5438aaaedca97b21cfa162021-11-25T19:05:57ZA New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy10.3390/sym131120052073-8994https://doaj.org/article/c45b89cf20d5438aaaedca97b21cfa162021-10-01T00:00:00Zhttps://www.mdpi.com/2073-8994/13/11/2005https://doaj.org/toc/2073-8994Analyzing 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.Chen LiangXiaofeng WangLei LuPengfei NiuMDPI AGarticlethe satisfiability problemstructure entropybelief propagation algorithmlabel propagation algorithmMathematicsQA1-939ENSymmetry, Vol 13, Iss 2005, p 2005 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	the satisfiability problem structure entropy belief propagation algorithm label propagation algorithm Mathematics QA1-939
spellingShingle	the satisfiability problem structure entropy belief propagation algorithm label propagation algorithm Mathematics QA1-939 Chen Liang Xiaofeng Wang Lei Lu Pengfei Niu A New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy
description	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.
format	article
author	Chen Liang Xiaofeng Wang Lei Lu Pengfei Niu
author_facet	Chen Liang Xiaofeng Wang Lei Lu Pengfei Niu
author_sort	Chen Liang
title	A New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy
title_short	A New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy
title_full	A New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy
title_fullStr	A New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy
title_full_unstemmed	A New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy
title_sort	new method for 3-satisfiability problem solving space structure on structural entropy
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/c45b89cf20d5438aaaedca97b21cfa16
work_keys_str_mv	AT chenliang anewmethodfor3satisfiabilityproblemsolvingspacestructureonstructuralentropy AT xiaofengwang anewmethodfor3satisfiabilityproblemsolvingspacestructureonstructuralentropy AT leilu anewmethodfor3satisfiabilityproblemsolvingspacestructureonstructuralentropy AT pengfeiniu anewmethodfor3satisfiabilityproblemsolvingspacestructureonstructuralentropy AT chenliang newmethodfor3satisfiabilityproblemsolvingspacestructureonstructuralentropy AT xiaofengwang newmethodfor3satisfiabilityproblemsolvingspacestructureonstructuralentropy AT leilu newmethodfor3satisfiabilityproblemsolvingspacestructureonstructuralentropy AT pengfeiniu newmethodfor3satisfiabilityproblemsolvingspacestructureonstructuralentropy
_version_	1718410304112558080

A New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy

Ejemplares similares