Abstract
This study investigates the transition between solvable and unsolvable instances in random $K$-Satisfiability ($K$-SAT) problems by treating the search for a solution as a dynamical process. Using finite-size scaling (FSS) techniques from statistical physics, the authors demonstrate that these transitions can be modeled as non-equilibrium "absorbing" phase transitions. By analyzing how solving time and the density of unsatisfied constraints scale with system size, they identify universal exponents that categorize different algorithms and problem types into distinct physical universality classes.
Introduction: The $K$-SAT Phase Transition
In theoretical computer science, $K$-SAT is a fundamental problem for assessing computational complexity. While $K \ge 3$ is NP-complete, random instances often exhibit a sharp phase transition: below a critical density of constraints ($\alpha_c$), problems are typically solvable (SAT), while above it, they are unsolvable (UNSAT).
In finite systems, these transitions are not perfectly sharp, complicating the determination of the exact threshold and the critical exponents describing system behavior near $\alpha_c$. This paper addresses this challenge by importing Finite-Size Scaling (FSS) from physics to extrapolate infinite-system behavior from finite data.
Methodology: Algorithms as Physical Processes
The researchers focused on Stochastic Local Search (SLS) algorithms, specifically ASAT (Average SAT) and RandomWalkSAT, which flip variable values to minimize unsatisfied (UNSAT) clauses. They modeled the "solved" state as an absorbing state in a physical system—once a solution is found, the dynamics cease.
Key indicators measured include the density of UNSAT clauses ($\rho_u$) and the median solving time ($\tau_H$). The authors applied an FSS ansatz accounting for system size ($N$) and distance from the threshold ($\epsilon$), crucially including logarithmic corrections necessary for high-dimensional or mean-field systems.
Results and Universality Classes
The study reveals that the phase transition is a property of the algorithm-problem pair rather than the problem alone. For $K=3$, different noise parameters in the algorithm lead to transitions at varying constraint densities. These transitions fall into known physical universality classes:
- Directed Percolation (DP): Observed in transitions like $K=3$ with RandomWalkSAT.
- Mean-Field Percolation: Observed in $K=2$ and optimized $K=3$ ASAT.
The authors found that for $K=2$, the transition consistently occurs at $\alpha_c = 1$ with a scaling exponent of $\bar{\nu} = 3$, matching mean-field percolation. For $K=3$, RandomWalkSAT reaches a solvability limit earlier ($\alpha_c \approx 2.67$) with Directed Percolation scaling ($\bar{\nu} = 2$). However, optimized ASAT pushes this limit to $\alpha_c \approx 4.18$, where scaling reverts to the percolation-type ($\bar{\nu} = 3$).
| Problem | Algorithm | Threshold ($\alpha_c$) | Scaling Exponent ($\bar{\nu}$) |
|---|---|---|---|
| 2-SAT | Any SLS | 1.00 | 3.0 |
| 3-SAT | RandomWalkSAT | 2.67 | 2.0 |
| 3-SAT | Optimized ASAT | 4.185 | 3.0 |
Conclusion and Future Directions
The value of the scaling exponent ($\bar{\nu}$) appears tied to the structure of the solution space—whether solutions are randomly scattered or clustered. The authors note that very small systems ($N < 10^3$) for $K=3$ do not yet exhibit true scaling behavior, explaining potential miscalculations in previous literature. Future work involves applying this FSS framework to other NP-complete problems, such as the Graph Coloring Problem (Q-COL), to explore the emergence of similar universality classes.
Summary updated