Fortnow: Fall's dramatic results show P vs NP still far from solved, as OpenAI proof dump yields first superlinear circuit lower bound

thomasahle · x · 2026-11-22

Complexity theorist Lance Fortnow (@fortnow) reissued his periodic reminder that a solution to P vs NP is not around the corner: this fall's dramatic results, while eye-catching, represent no real progress toward cracking P vs NP and only reinforce how hard the problem is.

Responding, thomasahle noted that OpenAI's proof dump did show the first superlinear circuit lower bound — improving from the known 3.1n to n√(log n) — and argued that extending this to n² and then 2^n would effectively settle the question.

The exchange captures a clash between optimists who see a path via circuit lower bounds and skeptics who maintain the problem remains far out of reach.

Original post →

More from Research

Research channel →