Ben Recht: how complexity theory forgot the problem it set out to solve
paraschopra · x · 2026-11-14
The source of the 3SAT dispute: Ben Recht's arg min post "Galactus the Devourer" examines the history of failing to rigorously define efficiency in computer science. Starting from Jack Edmonds' 1965 struggle to articulate what "efficient" means for his maximum matching algorithm, Recht describes a recurring applied-math pattern: modeling scaffolding spawns new puzzles that lure solvers away from the original problem, with complexity theory as the prime example — culminating in his critique of OpenAI's 3SAT subexponential claim, which only wins on inputs larger than anything physically possible.
Related event: OpenAI's 3SAT Claim Only Wins at Universe-Scale Variable Counts(2 posts)→
More from Research
- Xperience 2 turns real-world captures into interactive robot simulation environments — liuziwei7 · 2026-11-14
- Researcher Lets Claude Review His ICLR Paper's Reviews, and It Roasts the Community's Favorite Assumption — rao2z · 2026-11-14
- Flash ALOHA: robots learn fast, human-speed bimanual skills from 50 demos — erwincoumans · 2026-11-14
- MetaPI turns agent benchmarks into prompt-injection tests; best closed models still fail >20% of attacks — dair_ai · 2026-11-14
- rasbt maps Inkling 2 Small's 594B architecture built on attention residuals — rasbt · 2026-11-14
- Researcher builds a harness-specific LLM backdoor in hours on a local GPU, releases PoC — pgaleone · 2026-11-14