Accessibility vs Connectivity in SAT Solution Spaces: Geometry–Dynamics Role Inversion as a Diagnostic Principle
Abstract
Both SAT and galaxy data show that characteristic transition scales are marked by variance compression and maximal geometry–dynamics coupling, even when the detailed mechanism (inversion vs transition) differs. This work investigates the relationship between solution-space geometry and algorithmic dynamics in random 3-SAT, with the goal of distinguishing intrinsic structural properties from observer-dependent artifacts. We introduce metric rigidity as a geometric diagnostic measuring the minimum step size required to connect satisfying assignments, and compare its behavior under two complementary regimes: dynamic probing (greedy navigation of the solution space) and frozen dynamics (static connectivity analysis). Contrary to an initial geometry-primary hypothesis, we find that static connectivity and dynamic accessibility exhibit opposite trends across the clause-density transition. As clause density increases, the solution space becomes easier to connect globally yet harder to navigate locally. This inversion demonstrates that connectivity and accessibility are distinct properties, and that apparent rigidity arises from the interaction between geometry and dynamics, not from geometry alone. The results show that bottleneck-like signatures previously attributed to intrinsic solution-space structure are in fact dynamic in origin, emerging when algorithms operate under limited local information. By exchanging which subsystem is constrained—geometry or dynamics—the locus of observed structure shifts accordingly. This establishes a role-exchange principle: rigidity is not absolute but localizes where degrees of freedom are most restricted. The study provides a falsifiable framework for separating geometric structure from algorithm-induced effects and clarifies how phase-transition signatures can arise without bifurcation. While no complexity-theoretic claims are made, the findings constrain interpretations of algorithmic hardness and emphasize the necessity of analyzing geometry–dynamics coupling rather than either component in isolation.
Fields of Study & Subjects
Constraint Satisfaction and Optimization
Theoretical and Computational Physics
Advanced Graph Theory Research
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 12 January 2026