Ryan Williams on why P vs NP likely won't be proved soon, even with AI help
rrwilliams · x · 2026-11-23
MIT theoretical computer scientist Ryan Williams lays out possible fates of P vs NP:
- If P≠NP: a proof is unlikely soon even with AI-accelerated math. We'd likely first need progress on P≠PSPACE or LOGSPACE≠NP, both nearly stalled; circuit lower bound routes (proving SAT on length-L instances lacks L^1.01-size circuits, i.e. NP∉P/poly) are even further out.
- Third option: P vs NP might be unresolvable in standard math like ZFC — but he sees this as least likely, noting no reason the question is logically "more complex" than related statements like ETH or "SAT isn't in linear time and logspace." NP∉P/poly may be more vulnerable to such issues since the "computer" is an infinite description.
Related event: Ryan Williams lays out three scenarios for P vs NP(4 posts)→
More from AGI Musings
- User asks Anthropic to publish a full human-agent trace of solving a Millennium Prize problem — _arohan_ · 2026-11-23
- LeCun cites Socrates' opposition to writing to counter AI capability worries — ylecun · 2026-11-23
- ENIGMA Q&A: Why Open Datasets Made Alzheimer's AI Classification Nearly Solved — PTenigma · 2026-11-23
- Mustafa Suleyman and Yuval Harari discuss AI, consciousness and humanity — krishnan · 2026-11-23
- Polymarket: Only 10% odds US enacts AI safety bill by end of 2026 — Polymarket · 2026-11-23
- OpenAI Chief Scientist warns AI could spark 'avalanche' of breakthroughs by 2027 — Polymarket · 2026-11-23