2026-09-24
Notre Dame 把 k-SAT 写成一组常微分方程，解对应吸引子。约束密度过阈值后轨迹变瞬态混沌、盆界分形。冻结相连续时间按 N^1.66，但能量指数涨落，数字积分步数仍指数。
k-SAT 是 NP-complete 的原型：N 个布尔变量、M 条各含 k 个文字的子句，找一组赋值让全部为真。解可以多项式时间核对，已知找解算法最坏都是指数。约束密度 α = M/N 太低好找，太高容易判定不可满足；难的是中间段，尤其贴着可满足阈值。
随机 3-SAT 的可满足阈值 αs ≈ 4.26，冻结点 αf ≈ 4.25。过了 α = 4.21，已知局部搜索基本变指数或直接失败；Survey Propagation 过 4.25 也失效。Gu、Nagamatu、Wah 等人把 SAT 写成连续优化或模拟动力系统，直接最小化能量 E 会被非解吸引子困住。这篇要一套不卡死、还能把「难」翻译成可观测动力学量的连续时间系统。
布尔变量 xi 换成连续自旋 si ∈ [-1, 1]，si = ±1 对应真假。第 m 条子句写成 Km(s) = 2^{-k} ∏i (1 - cmi si)，Km = 0 当且仅当该子句被满足。朴素能量 E = Σ Km² 的全局零点就是 SAT 解，但它有坑。
改成带辅助变量的 V(s, a) = Σ am Km²，am > 0，作用类似拉格朗日乘子。动力学两条：
辅助变量可以消掉：am(t) = am(0) exp(∫ Km dτ)。一直不满足的条款会越来越用力推自旋。s 被锁在超立方 [-1, 1]^N 里；SAT 解是吸引不动点；没有极限环；可满足公式的稳定吸引子只可能是 V = 0。落在某个解所在卦限、且 |s|² ≥ N - 1 + (k-1)²/(k+1)² 的点，保证流进那个解。
确定性带来几何：每个初值对应唯一轨迹，把 HN 按「最终流进哪个解簇」上色，得到吸引盆。公式对应的超图去掉纯文字后若剩下核（core），自旋方程互相耦合，轨迹可以变混沌，盆界变分形。可满足时吸引子还在，这种混沌只能是瞬态的。3-XORSAT 里混沌核是一个有限超图，混沌阈值与 Mézard 等人算的动力学相变 γd = 0.8185 重合。
冻结相里，到连续时间 t 仍未解出的公式比例 p(t) = r e^{-λ(N) t}，λ(N) = b N^{-β}。
| 集合 | 设定 | β | 规模 |
| 随机 3-SAT | α = 4.25 | ≃ 1.66 | N = 20-150，每档 10^5 实例 |
| +1-in-3-SAT | l = 2.34 | ≃ 1.68 | N = 20-80，每实例 10 个初值，10^4 实例 |
解出固定比例所需连续时间 t(p, N) = b^{-1} N^β ln(r/p)，对 N 是幂律。补充材料把「漏掉固定条数」也推成 N^{β+1} ln N。轨迹在 HN 里的长度同样按幂律长。
数字机上不是这么回事。五阶自适应 Cash-Karp Runge-Kutta 要把离散点钉在真轨迹一根细管里，硬实例上 nstep 会指数爆。p(nstep) ≈ u(v + nstep)^{-η}，η(N) = d N^{-δ}，δ ≃ 1.09，漏掉比例 p 所需步数对 N 指数。容易相（α = 3，N = 5000）里 p(nstep) 跟 p(t) 一样指数衰减，离散也是多项式。
N = 200 的例子：α = 3 大约 t = 8.2 找到解；α = 4.25 要 t = 96.4，轨迹已是混沌；α = 4.5 的不可满足实例能量不落地。冻结相的盆界还出现 Wada 性质：边界点同时挨着至少三个吸引盆，数值误差可能把轨迹甩到 Hamming 距离 O(N) 的另一个簇。
这是 2011 年 Nature Physics 的一封 Letter，把 NP 问题的「难」写成瞬态混沌的逃逸率 κ：κ^{-1} 可以当单条公式的硬度。对做 SAT、统计物理、模拟计算的人，它给了一张相变地图：层流盆界对应容易，分形盆界对应难，混沌阈值可以跟核、动力学相变对齐。
它没有把 P vs NP 打穿。连续时间多项式，靠的是允许能量 V 和辅助变量指数涨。换成数字积分，冻结相仍指数。真要吃到多项式，需要能物理实现无界动态范围的模拟器件；论文只是提示这条路，没有给出电路。
对现在做连续松弛、神经 SAT、ODE 求解器的人，工程教训仍在：正反馈权重能把搜索抬出局部井，但井之间的分形边界会把数值误差放大成指数步数。这是渐进的概念贡献，不是能直接上生产的求解器。
「可满足就一定找到解」写的是分析加模拟，不是完整证明。补充材料 E.1 节承认，轨迹必离开无解区域只是证明提纲，「正式证明另文」；到这篇为止，非解混沌吸引子被排除的论证并不闭合。双曲性也是猜想，用来解释逃逸为何指数。
模拟规模有限：冻结 3-SAT 到 N = 150，+1-in-3-SAT 到 N = 80，N = 5000 只出现在容易相。指数步数对上幂律连续时间的反差，在更大 N 上会不会被 RK 误差或 Wada 切换改写，论文没给出。能量指数涨落意味着模拟硬件同样要扛指数动态范围，这一点被一笔带过。方程形式也不唯一，同一原则下别的 ODE 可能同样能跑。