Random k-sat solutions connect by single flips below key density thresholds
Single-Variable Connectivity in Random $k$-SAT
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The paper studies how solutions to a complex logical puzzle called random k-SAT are connected and change as you adjust the number of rules. The authors show that up to a certain point, you can move between solutions by flipping one variable at a time in a way that always keeps the puzzle solvable. They identify precise mathematical thresholds where the solution space changes structure—from connected, to clustered, to rigid where flipping variables becomes hard. This deepens understanding of the puzzle’s structure and transitions as its difficulty increases.
What this means in practice
- •For constraint solver developers: Design algorithms that efficiently explore solution spaces by flipping single variables within satisfiable regions up to certain problem densities.
- •For combinatorial optimization engineers: Use the identified density thresholds to predict when solution spaces fragment, aiding heuristics for problem instances in scheduling or design.
A theory result. No direct application yet.
Authors
Chunyang Wang, Yitong Yin, Yixiao Yu, Yiyao Zhang
Abstract
We resolve longstanding questions about connectivity, reconstruction,and looseness in random $k$-SAT, for sufficiently large fixed $k$ as the number $n$ of variables tends to infinity. $\textbf{Single-variable connectivity up to reconstruction.}$ At clause densities up to \[\frac{2^k}{k}\bigl(\ln k+\ln\ln k+γ_*-o_k(1)\bigr),\] a polynomial-time algorithm joins a typical pair of satisfying assignments with high probability, using $O_k(n)$ single-variable flips that preserve satisfiability. Here $γ_*\approx0.871$ arises from a refined tree-reconstruction analysis. $\textbf{Settling the reconstruction threshold.}$ Building on the tools developed for connectivity, we determine the clustering threshold defined by the reconstruction criterion to be \[\frac{2^k}{k}\bigl(\ln k+\ln\ln k+γ_*+o_k(1)\bigr),\] below the classical cavity prediction with constant term $1+O(\ln\ln k/\ln k)$. $\textbf{Shattering before rigidity.}$ We locate the looseness--rigidity transition at a higher density, matching the classical cavity prediction for clustering: \[\frac{2^k}{k} \left(\ln k+\ln\ln k+1+Θ\left(\frac{\ln\ln k}{\ln k}\right)\right).\] Below the transition, we establish a stronger form of looseness: any variable of a typical solution can be reversed by logarithmically many single-variable flips that preserve satisfiability. Above it, reversing most variables of a typical solution requires changing linearly many variables (rigidity). Yet throughout an interval between reconstruction and rigidity, the solution space already splits into groups of exponentially small relative size separated by linear Hamming distance and linear energy barriers (shattering), while logarithmic looseness persists.