OpenAI says its models disproved the Exponential Time Hypothesis and proved local smoothing in every dimension
- OpenAI says its models produced a deterministic algorithm that exactly counts the satisfying assignments of an arbitrary k-CNF formula in superpolynomial but subexponential time, the result it headlines as The Exponential Time Hypothesis is false.
- Models proved the local smoothing conjecture in every dimension, which the announcement says also settles the Kakeya conjecture and Stein's restriction conjecture in all dimensions; the proof rests on a novel auxiliary partial differential equation, the AI output came on October 18, 2026, and Lean formalization followed the next day.
- A third result covers existence of quantum chromodynamics and completions of the Standard Model, with OpenAI noting a natural language proof for Yang-Mills existence dated September 9, 2026; commenters point out the mass gap is not part of the claim.
- OpenAI had external experts act as shepherds and let them pick three different release strategies: the math output goes out as-is, the computer science group publishes the natural language proof and Lean formalization on GitHub immediately, and the physics group chose to withhold AI artifacts and write the result up itself.
- Collaborators join voluntarily and unpaid, sign no NDAs, and OpenAI states it seeks no academic credit for discoveries made by its models, while the working groups keep credit for the explanations they write.
Hacker News 의견들
The title buries the lede hard. One of the three items is literally "The Exponential Time Hypothesis is false" and it shows up third.
Wait, does that mean SETH is false too? I'm in way over my head here.
The CS preprint gives a deterministic algorithm for exactly counting satisfying assignments of an arbitrary k-CNF formula in superpolynomial but subexponential time. What a time to wake up to.
I get that ETH being false doesn't imply P=NP, but does this move anyone's priors? Are you all updating toward P=NP?
Not really, for me. The time bound is of the form 2^{n/polylog(n)}, which is subexponential, and if a reduction blows instance size up quadratically you land back outside it. The boundary in the hypothesis was kind of arbitrary, so breaching it doesn't change much.
I think it has to move your belief. Any new implication of P=NP should raise your confidence in the two classes being equal. I used to cite ETH as a throwaway conjecture in a side note, so this is a big Bayesian update.
Scott Aaronson said it took him from 3% to 5% on P=NP, which is more generous than I'd be.
Read the actual announcement before the takes fly. It's three results: local smoothing and Kakeya, ETH is false, and existence of QCD plus completions of the Standard Model.
I looked for a substantial contribution from OpenAI and found a $5 million donation to a research foundation. That sustains maybe 5 to 10 PhD students for five years while everyone else burns time verifying the output.
Nobody is forcing anyone to verify it.
They also got a natural language proof for Yang-Mills existence on September 9, 2026, and it sure looks like the mass gap part is missing. These were big swings at all the Millennium Prize problems.
Worth noting the proof looks like sub-exponential #3-SAT, not just 3-SAT, which is the stronger statement.
Isn't 3-SAT NP-complete though?
For context on the ETH side: it's been a hardness assumption in hundreds of papers, so a disproof undercuts a large body of complexity results and changes what people think is efficiently computable. Kakeya had been going one dimension at a time, so settling every dimension at once is a different scale.
I have several papers that assume ETH myself. Honestly the fun part is that a whole pile of open problems just appeared.
My cynical read: the results are too important to wait for peer review, so drop money in a fund and give some chosen people a first look. Science is a grind with thousands of results a year going through review, and treating every model output like a revelation gets tiring.
Science doesn't have to be a grind if AI is doing the checking.
Tao versus 3B1B on this is already causing a kerfuffle in the departments. This is the new normal.