Fortnow revisits 3SUM, APSP and ETH: why complexity conjectures are believed
fortnow · x · 2026-11-02
Theoretical computer scientist Lance Fortnow republishes a two-year-old essay on the Computational Complexity blog examining why the 3SUM, APSP and ETH conjectures are widely believed.
- 3SUM: given integers, decide if any triple sums to zero; best known algorithm is O(n²), and the community conjectures no subquadratic algorithm exists. About 15-20 known 3SUM-complete problems stand or fall together.
- He draws parallels to the P≠NP belief: decades of failed attacks and reduction chains form compelling though non-mathematical evidence.
- Framed around recent claimed proofs by OpenAI and Anthropic, the post uses history to understand how we reason about hardness in the present.
More from Research
- Thurston's 1994 warning revived: theorem-credit culture may hurt math as AI automates proofs — alexbilz · 2026-11-02
- AI text detection study: input:output length ratio raises miss rate by at most 5% — amplifiedamp · 2026-11-02
- Blogger Speculates on a Continual Learning Architecture Combining Multi-Stream LLMs and ECHO — joey072shx · 2026-11-02
- L3G-World Generates Minute-Long Consistent Worlds From a Single Image — Crazy-Repeat-2006 · 2026-11-02
- Why LLM steerability beats specialized models in generative bio design pipelines — chaitjo · 2026-11-02
- Epoch AI figure output growing 1.6x per year — the only 'wall' is November's zero — SamuelAlbanie · 2026-11-02