Optimization hardness as transient chaos in an analog approach to constraint satisfaction

作者：Ercsey Ravasz Maria^*; Toroczkai Zoltan

来源：Nature Physics, 2011, 7(12): 966-970.

DOI：10.1038/NPHYS2105

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), signalling 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 (ref. 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.

• 出版日期2011-12