Loading...
Please wait, while we are loading the content...
Similar Documents
A New Method for 3-Satisfiability Problem Solving Space Structure on Structural Entropy
| Content Provider | MDPI |
|---|---|
| Author | Liang, Chen Wang, Xiaofeng Lu, Lei Niu, Pengfei |
| Copyright Year | 2021 |
| 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. |
| Starting Page | 2005 |
| e-ISSN | 20738994 |
| DOI | 10.3390/sym13112005 |
| Journal | Symmetry |
| Issue Number | 11 |
| Volume Number | 13 |
| Language | English |
| Publisher | MDPI |
| Publisher Date | 2021-10-22 |
| Access Restriction | Open |
| Subject Keyword | Symmetry Industrial Engineering the Satisfiability Problem Structure Entropy Belief Propagation Algorithm Label Propagation Algorithm |
| Content Type | Text |
| Resource Type | Article |
