Optimization hardness as transient chaos in an analog approach to constraint satisfaction
This addresses the challenge of efficiently solving NP-hard optimization problems like k-SAT, which has broad implications for computer science and algorithm design, but the approach is incremental as it builds on analog and dynamical systems methods.
The authors tackled the problem of solving hard Boolean satisfiability (k-SAT) optimization problems by mapping them into a deterministic continuous-time dynamical system, showing that it always finds solutions for satisfiable formulae in polynomial continuous-time, even in the hardest algorithmic benchmarks like random 3-SAT and locked occupation problems, though with exponential energy fluctuations.
Boolean satisfiability [1] (k-SAT) is one of the most studied optimization problems, as an efficient (that is, polynomial-time) solution to k-SAT (for $k\geq 3$) implies efficient solutions to a large number of hard optimization problems [2,3]. Here we propose a mapping of k-SAT into a deterministic continuous-time dynamical system with a unique correspondence between its attractors and the k-SAT solution clusters. We show that beyond a constraint density threshold, the analog trajectories become transiently chaotic [4-7], and the boundaries between the basins of attraction [8] of the solution clusters become fractal [7-9], signaling the appearance of optimization hardness [10]. Analytical arguments and simulations indicate that the system always finds solutions for satisfiable formulae even in the frozen regimes of random 3-SAT [11] and of locked occupation problems [12] (considered among the hardest algorithmic benchmarks); a property partly due to the system's hyperbolic [4,13] character. The system finds solutions in polynomial continuous-time, however, at the expense of exponential fluctuations in its energy function.