2026-09-24
They map k-SAT to ODEs whose attractors are solution clusters. In the frozen phase analog time scales as N^1.66, but exponential energy spikes keep discrete RK steps exponential.
k-SAT is the textbook NP-complete problem: N Boolean variables, M clauses of k literals each, find an assignment that satisfies every clause. Checking a candidate is polynomial; every known search algorithm is exponential in the worst case. When the constraint density α = M/N is small, solutions are easy to find. When it is large, unsatisfiability is easy to certify. The hard band sits in between, especially near the satisfiability threshold.
For random 3-SAT the SAT/UNSAT threshold is αs ≈ 4.26 and the freezing point is αf ≈ 4.25. Past α = 4.21 known local search methods turn exponential or fail; Survey Propagation fails past 4.25. Earlier continuous formulations by Gu, Nagamatu and Wah can stall in non-solution attractors of a naive energy E. The paper wants a continuous-time system that does not trap, and that turns hardness into a measurable dynamical quantity.
Each Boolean xi becomes a spin si ∈ [-1, 1], with ±1 for true and false. Clause m is encoded as Km(s) = 2^{-k} ∏i (1 - cmi si), which is zero exactly when the clause is satisfied. The naive energy E = Σ Km² has SAT solutions as global zeros, and plenty of traps.
They replace it with V(s, a) = Σ am Km², where auxiliary am > 0 play a Lagrange-like role. The ODEs are:
The auxiliaries can be integrated out: am(t) = am(0) exp(∫ Km dτ). Spins stay inside the cube [-1, 1]^N. SAT solutions are attracting fixed points. There are no limit cycles. For satisfiable formulas the only stable attractors are the global minima V = 0. Any point in the orthant of a solution with |s|² ≥ N - 1 + (k-1)²/(k+1)² is guaranteed to flow into that solution.
Because the flow is deterministic, every initial condition has a unique trajectory. Color HN by which solution cluster the orbit ends in, and the basins fill the cube except a measure-zero basin boundary. Once the formula's hypergraph has a core after pure-literal removal, the spin equations couple, orbits can become chaotic, and basin boundaries turn fractal. The attractors still exist for SAT instances, so the chaos is transient. In 3-XORSAT the chaotic core is a finite hypergraph, and the chaos threshold coincides with Mézard's dynamical transition at γd = 0.8185.
In the frozen phase the fraction of formulas still unsolved by continuous time t decays as p(t) = r e^{-λ(N) t}, with λ(N) = b N^{-β}.
| ensemble | setting | β | scale |
| random 3-SAT | α = 4.25 | ≃ 1.66 | N = 20-150, 10^5 instances each |
| +1-in-3-SAT | l = 2.34 | ≃ 1.68 | N = 20-80, 10 initial conditions, 10^4 instances |
Time to solve a fixed fraction is t(p, N) = b^{-1} N^β ln(r/p), a power of N. The supplement pushes the "leave a constant number unsolved" case to N^{β+1} ln N. Trajectory length in HN also scales as a power.
On a digital machine the picture changes. A fifth-order adaptive Cash-Karp Runge-Kutta integrator must keep discrete points inside a thin tube around the true orbit; for hard instances nstep explodes. They fit p(nstep) ≈ u(v + nstep)^{-η} with η(N) = d N^{-δ} and δ ≃ 1.09, so the step count needed to miss only a fraction p is exponential in N. In the easy phase (α = 3, N = 5000) p(nstep) decays exponentially like p(t), so the discretized algorithm is polynomial there too.
A N = 200 example: α = 3 finds a solution at t ≈ 8.2; α = 4.25 needs t = 96.4 with a chaotic orbit; an unsatisfiable instance at α = 4.5 never lands. Frozen-phase basin boundaries can have the Wada property: a boundary point sits on at least three basins at once, so numerical error can kick the orbit toward another cluster a Hamming distance O(N) away.
This 2011 Nature Physics Letter writes NP hardness as an escape rate κ of transient chaos: κ^{-1} is a per-formula hardness. For SAT, statistical physics, and analog computing, it supplies a phase map: laminar basins for easy instances, fractal basins for hard ones, with the chaos threshold lining up with cores and dynamical transitions.
It does not crack P vs NP. Polynomial analog time is bought by letting V and the auxiliaries grow exponentially. On a digital integrator the frozen phase stays exponential. Getting that polynomial in hardware would require analog devices with unbounded dynamic range; the paper points at that path and does not build a circuit.
For anyone doing continuous relaxations, neural SAT, or ODE solvers, the engineering moral still holds: positive-feedback weights can lift a search out of a local well, and fractal boundaries between wells turn integration error into exponential step counts. This is a conceptual increment, not a production solver.
"Always finds a solution if one exists" is analysis plus simulation, not a closed proof. Supplement E.1 calls the escape-from-any-non-solution-domain argument a sketch, with a full proof "to be published elsewhere." Exclusion of non-solution chaotic attractors is therefore incomplete in this paper. Hyperbolicity is a conjecture used to explain the exponential escape.
Simulation scale is modest: frozen 3-SAT to N = 150, +1-in-3-SAT to N = 80, N = 5000 only in the easy phase. Whether RK error or Wada switching rewrites the exponential-versus-power contrast at larger N is untested. Exponential energy swings imply that analog hardware would still need exponential dynamic range; that cost is mentioned more than measured. The ODE form is not unique; other equations on the same principle might work as well.