2012/08/02 by Maria Ercsey-Ravasz, Zoltan Toroczkai · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #cs.CC #cs.NE #math.DS #nlin.CD #physics.comp-ph #msc:37D45 #msc:90C27 #msc:68Q10 #msc:68Q17 #msc:34G20 #acm:37D45 #acm:90C27 #acm:68Q10 #acm:68Q17 #acm:34G20
paper · pdf · doi:10.1038/nphys2105
published as Nature Physics, vol. 7, p. 966-970, 2011 · 27 pages, 14 figures
arxiv created 2012/08/02 · arxiv updated 2012/08/03
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≥ 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.