OpenAI's 3SAT subexponential proof only kicks in above universe-scale variable counts
paraschopra · x · 2026-11-14
Paras Chopra highlights a counterintuitive catch in OpenAI's recent subexponential-time 3SAT claim: the algorithm only beats brute force above 10^(2×10^10) variables (a 20-billion-digit number) and beats today's best 3-SAT algorithms only above 10^(3.5×10^11) — while the observable universe has just 10^80 atoms. For any physically realizable input it degenerates to brute force or known exponential algorithms. The argument comes from Ben Recht's arg min post tracing how complexity theory lost sight of the original problem after Edmonds' 1965 definition of "efficient."
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