Optimization hardness as transient chaos: revisiting a classic Nature Physics k-SAT paper
wgilpin0 · x · 2026-09-24
A thread revisits dynamical-systems approaches to combinatorial optimization: mid-1990s to 2005 work framed problems like TSP and channel assignment as Hopfield networks minimizing energy.
The core citation is Ercsey-Ravasz & Toroczkai's 2011 Nature Physics paper mapping k-SAT to a deterministic continuous-time dynamical system: beyond a constraint-density threshold, trajectories become transiently chaotic and solution-basin boundaries turn fractal, signaling hardness—yet the system still finds solutions in polynomial time even in frozen 3-SAT regimes.
More from Research
- 3DV Citation Grand Prix: 2016 Monocular Depth Paper Hits 2,793 Citations — CSProfKGD · 2026-09-24
- Pioneer Labs engineers first bacteria to turn Mars atmosphere and soil into bioplastic — 2C_ornot2C · 2026-09-24
- Epoch AI audit finds 46% of sampled Humanity's Last Exam questions are defective — geoffwolfe · 2026-09-24
- Semantic operators: LLM data processing at scale needs full-stack rethink — CShorten30 · 2026-09-24
- Jev processes 100k rows for $2.50 in under 60s, demo now public — CShorten30 · 2026-09-24
- CLM-8B hits SOTA 81.6% on DeepSWE with light finetuning, up to 9x faster inference — anshulkundaje · 2026-09-24