P≠NP won't be proved soon, but AI could speed the needed literature 100x

rrwilliams · x · 2026-11-23

rrwilliams' second scenario: even with AI acceleration, P≠NP almost certainly won't be proved soon. Easier separations like P≠PSPACE or LOGSPACE≠NP must fall first (barely any progress), and circuit lower bounds are further out — prove SAT of length L has no L^1.01-size circuits first. He believes AI will speed up building that thin literature by orders of magnitude.

Related event: Ryan Williams lays out three scenarios for P vs NP(4 posts)→

Original post →

More from AGI Musings

AGI Musings channel →