The Exponential Time Hypothesis is False

Community
,
1

OpenAI comes out with a new computer science/mathematics proof regarding the ETH.

I’m going to make it my goal to understand this thoroughly, but for now, my interpretation is that for extremely complex problems, that previously required exponential time solutions, they claim to have found an algorithm whose running time is subexponential.

I don’t think it solves P-vs-NP, it doesn’t break all encryption, and it doesn’t make every computing problem solvable. But it does claim to prove that our limits on time computation are now different.

Link to pre-print paper (PDF): math/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf at main · openai/math · GitHub

2

image
image1212×192 16 KB

3

I think this is a strong proof point for AI-driven research itself.

If the result holds up under Lean formal verification and independent mathematical scrutiny, it sets an important precedent: AI can augment and advance our existing research institutions rather than replace them.

To me, that’s potentially as significant as the mathematical discovery itself.