Optimization hardness as transient chaos in an analog approach to constraint satisfaction
Optimization hardness as transient chaos in an analog approach to constraint satisfaction
复制标题
DOI：
10.1038/nphys2105
复制
发表时间：
2011-12-01
期刊：
影响因子：
19.6
通讯作者：
Toroczkai, Zoltan
中科院分区：
文献类型：
--
作者：
Ercsey-Ravasz, Maria;Toroczkai, Zoltan
布尔可满足性(1)(k-SAT)是研究最多的优化问题之一，因为k-SAT(k>；=3)的有效解(即多项式时间)蕴含着大量困难优化问题(2，3)的有效解。在这里，我们提出了k-SAT到确定性连续时间动力系统的映射，它的吸引子与k-SAT解簇之间具有唯一的对应关系。我们表明，超过约束密度阈值，模拟轨迹变得瞬时混沌(4-7)，解集群的吸引盆地(8)之间的边界变得分形(7-9)，表明优化硬度的出现(10)。分析论证和模拟表明，即使在随机3-SAT(参考文献)的冻结区域，系统也总是能找到可满足公式的解。11)和锁定占用问题(12)(被认为是最困难的算法基准之一)，这一性质部分是由于系统的双曲性(4，13)。然而，该系统以其能量函数的指数波动为代价，在多项式连续时间内找到解。
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.