Ryan Williams: OpenAI's ETH-violating solver fits the "split and list" algorithm class
rrwilliams · x · 2026-10-30
Reacting to OpenAI's purported ETH-violating solver, theoretical computer scientist Ryan Williams says it belongs to a class he calls "split and list": break variables into pieces, enumerate all assignments within pieces, and use a P problem to stitch them together, reducing an NP problem to an exponentially large P instance.
More from Research
- New paper asks why teams of AI agents fail where a single agent often matches them — JoshPurtell · 2026-10-30
- Prime Intellect makes DeepSeek's MegaMoE trainable, up to 55% faster MoE training — samsja19 · 2026-10-30
- CMU Releases SwarmChat, an Open-Source Slack for AI Agent Swarms — niloofar_mire · 2026-10-30
- Top robotics data companies are applied research labs: ego-data post-training beats Apple EgoDex — ATTlKA · 2026-10-30
- Prime Intellect Residents Release Fully Open Agent Evals: MazeBench, PretrainGym, OpenTTD-Bench — xeophon · 2026-10-30
- DreamFAR world model trained from scratch on robot data only, ~$110k in H200 hours — k7agar · 2026-10-30