求解困难度即瞬态混沌：Nature Physics 经典论文重现 discussions

wgilpin0 · x · 2026-09-24

讨论串回顾了用动力系统方法解组合优化问题的研究脉络：90 年代中期到 2005 年间，有研究将 TSP、通信信道分配等组合优化问题形式化为 Hopfield 神经网络并让其最小化能量来求解。

核心引用是 Ercsey-Ravasz 与 Toroczkai 2011 年发表于 Nature Physics 的论文：将 k-SAT 映射为确定性连续时间动力系统，证明当约束密度超过阈值后，模拟轨迹变为瞬态混沌，解簇吸引域边界呈分形结构——这正是求解困难度的信号；即使在最难的冻结区，系统仍能对可满足公式在多项式时间内找到解。发帖人认为在该设定下分形不可避免。