Speaker
Prof.
Zoltan Toroczkai
(University of Notre Dame)
Description
Boolean satisfiability (k-SAT) is one of the most studied
optimization problems, as an efficient (polynomial-time)
solution to k-SAT (for k > 2) implies efficient solutions to
a very large number of hard optimization problems. 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, and the boundaries between the
basins of attraction of the solution clusters become
fractal, signalling the appearance of optimization
hardness. The system always finds solutions for
satisfiable formulas and simulations indicate that it finds
them in polynomial continuous-time even in the frozen
regimes of random 3-SAT and of locked occupation
problems; a property partly due to the system’s
hyperbolic character. In terms of the number of
discretization steps, however, the complexity of the
computation via digital (Turing) machines is exponential
for hard instances due to the strongly chaotic nature of
the analog trajectories.
With: M. Ercsey-Ravasz
Reference: Nature Physics, vol. 7, 966-970 (2011).
Primary author
Prof.
Zoltan Toroczkai
(University of Notre Dame)
