Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Other literature type . 2026
License: CC BY
Data sources: ZENODO
ZENODO
Other literature type . 2026
License: CC BY
Data sources: Datacite
ZENODO
Other literature type . 2026
License: CC BY
Data sources: Datacite
versions View all 2 versions
addClaim

The Paradoxical Closed Loop Spectral Barriers, Treewidth Geometry, and Boundary-Validated SAT Solving

Authors: Paradise, Chris;

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.

Keywords

Satisfiability, Computational Complexity, Treewidth, Graph Separators, Paradoxical Closed Loop, Spectral Washout, Local Repair Dynamics, Instance-Independent Mixing, Expansion vs. Separators, Incidence Graphs, Nice Tree Decompositions, Boundary-Validated Dynamic Programming, Bounded-Treewidth SAT, Parameterized Algorithms, Total Variation Contraction

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Green