Why ETH being false wouldn't make all of NP sub-exponential: reductions add polynomial factors
robleclerc · x · 2026-10-28
LDanilek revisits a complexity-theory intuition: at first it seems that if ETH is false, all NP problems admit sub-exponential algorithms — just reduce any NP problem to NP-complete 3-SAT and solve sub-exponentially. But reductions can introduce polynomial factors: if an NP problem reduces to a cubic-sized 3-SAT, the best known solution remains exponential. The author is relieved for now but suspects more innovation is coming now that the barrier has been breached.
More from Research
- UCLA and Tsinghua paper probes how far coding agents can go in visual generation — ucla-cmllab · 2026-10-28
- Author credits Claude and ChatGPT for writing most of his Stanford medical AI thread — jonc101x · 2026-10-28
- What would it take to trust an AI agent to carry out clinical work tasks? — jonc101x · 2026-10-28
- Medical AI is weakest at clinical decision support and admin workflows — exactly where hospitals need it most — jonc101x · 2026-10-28
- GPT-5.5 passes 46.3% of clinical tasks once, but only 28% across three runs — jonc101x · 2026-10-28
- Stanford's 3-year medical AI benchmark review: GPT-5.5 drops to 28% when tasks must succeed 3 runs in a row — jonc101x · 2026-10-28