Ladner's theorem view on NP-intermediate problems: the subexponential-algorithm guess falls apart
yacineMTB · x · 2026-10-27
Reacting to a new complexity result, Peter Schmidtnelson notes that Ladner's theorem implies P≠NP would make NP-intermediate problems non-empty. He had long assumed NPI problems would be the ones with subexponential algorithms (possibly in BQP), while NP-complete problems would have none — apparently not the case.
More from Research
- Map of secure program synthesis: ruby-lean in Lean and the race to formally verify everything — burny_tech · 2026-10-27
- OpenAI claims rigorous Yang-Mills existence proof; physicist Woit calls the announcement misleadingly vague — burny_tech · 2026-10-27
- Researcher corrects 'Uncheatable forecast': admits flop-uncontrolled compute estimate — dlwh · 2026-10-27
- Buzz grows over claimed subexponential 3SAT and what it would mean for NP problems — burny_tech · 2026-10-27
- OpenAI internal model claims to refute ETH; Impagliazzo, Paturi and Williams to organize independent review — aminkarbasi · 2026-10-27
- D3-Gym: first auto-constructed verifiable environments for data-driven scientific discovery, shown at EMNLP 2026 — hhsun1 · 2026-10-27