The Paradoxical Closed Loop Spectral Barriers, Treewidth Geometry, and Boundary-Validated SAT Solving
Abstract
This paper introduces the Paradoxical Closed Loop (PCL) framework for analyzing cyclic algorithms that repeatedly apply (i) local, non-oracular repair based on the instance, (ii) instance-independent mixing that contracts toward a reference distribution, and (iii) optional validation/filtering. Under explicit locality and contraction assumptions, we prove a spectral washout no-go theorem: for satisfiable CNF families with exponentially small satisfying fraction, any polynomial number of PCL cycles preserves only exponentially small probability mass on satisfying assignments, preventing polynomial-time amplification by this class of dynamics. We interpret the obstruction geometrically as a conflict between global enforcement (expansion) and separator compressibility (bounded treewidth). This motivates a constructive escape: for formulas whose incidence graphs have bounded treewidth, we give BVH-SAT, an exact solver based on nice tree decompositions and boundary-validated dynamic programming, running in O((n+m)\cdot 2^{O(k)}) time for width k, with an optional correctness-preserving stochastic prioritization layer.
Fields of Study & Subjects
Advanced Graph Theory Research
Constraint Satisfaction and Optimization
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 14 January 2026