Local Search Optimization for 3-SAT Based on Graph Laplacian Spectral Feedback and Topological Collapse

Abstract:The Boolean Satisfiability Problem (3-SAT) exhibits extreme computational complexity in the phase transition region, where traditional local search algorithms frequently get trapped in severe local minima due to Replica Symmetry Breaking (RSB). Based on the Regional Locking Inference (RLI) framework, this paper proposes an improved local search algorithm based on Graph Laplacian spectral feedback and adaptive topological collapse (A1-Collapse). By monitoring the topological tension of the constraint network in real-time, the algorithm forces local tensor contraction on high-connectivity core clusters when the system stagnates. Numerical experiments on N=100 demonstrate that in the hard phase transition region (3.4 < α < 4.0), the A1-Collapse algorithm successfully tears through local minima, significantly outperforming traditional heuristic algorithms in success rates (e.g., 40% vs 30% at α=3.43). 摘要:布尔可满足性问题(3-SAT)在相变临界区表现出极端的计算复杂性,传统局部搜索算法常因解空间的复制对称破缺(RSB)而陷入严重的局部极小值。本文基于区域锁定推断(RLI)框架,提出了一种基于图拉普拉斯谱反馈与自适应拓扑坍缩(A1-Collapse)的改进型局部搜索算法。通过实时监测约束网络的拓扑张力,在系统陷入停滞时强行对高连通度核心簇实施局部张量缩并。在有限尺寸(N=100)的数值实验中,相图结果表明:在相变困难区,A1-Collapse 算法成功撕裂局部极小值,求解成功率显著反超传统启发式算法(如 α=3.43 时 40% 对 30%)。