OpenAI's AI Claims It Broke a 27-Year-Old Rule of Computing. The Rule's Inventors Are Checking.

In 1999, two computer scientists, Russell Impagliazzo and Ramamohan Paturi, wrote down a hunch about a kind of puzzle. They thought one family of logic puzzles would stay brutally hard for computers no matter how clever anyone got. Their hunch got a name, the Exponential Time Hypothesis, and over the next quarter century it quietly became one of the load-bearing walls of computer science.

On Monday afternoon, OpenAI posted a 67-page paper to its public GitHub page with a blunt title: "The Exponential Time Hypothesis is False."

The paper wasn't written by a person. OpenAI's account is that an unreleased, in-house AI model found the argument on October 16, and that the company had a computer proof-checker confirm it the next day. And the people OpenAI asked to lead the checking are Impagliazzo and Paturi themselves, both now at UC San Diego, joined by MIT's Ryan Williams. Picture being asked to referee a paper that claims your best-known idea is wrong, written by a machine you don't have access to. That's roughly where they are this week.

Nobody has confirmed the result yet. Its three referees went out of their way to make that point, in writing, on the same afternoon the paper appeared. It's still one of the stranger moments in the short, chaotic history of AI doing math, and the puzzle at the center of it is simpler than it sounds.

A puzzle made of light switches

Imagine a row of light switches, each one either on or off. You also get a list of rules, and every rule names three switches and demands that at least one of them be set a certain way. Something like "switch 4 on, or switch 9 off, or switch 12 on." Your job is to find a way to set every switch so that all the rules are happy at once, or to prove that no such setting exists.

Computer scientists call this 3-SAT. It sounds like a toy, and with five switches it is one. You could try every combination in your head. The trouble is how fast "every combination" grows. Each new switch doubles the number of possible settings. Every one. Ten switches give you 1,024 combinations; fifty give you more than a quadrillion. A hundred switches give you a number with 31 digits. A computer checking a billion settings every second would need about 40 trillion years to get through them all, which is roughly 3,000 times the age of the universe.

That doubling is what "exponential" means here. One more switch, twice the work.

The puzzle matters because plenty of other problems can be translated into switches and rules. Solve the switches and you've solved the original problem. Puzzle-solving programs built on clever guessing have been tested on real engineering puzzles from circuit design and fault diagnosis, and they've shown practical value there. The question theorists care about is the worst case, the nastiest possible puzzle someone could build.

The rule everyone built on

Brute force means checking every setting, which costs you a doubling per switch. Smart people found shortcuts. In 1999, the same year as the hypothesis, the computer scientist Uwe Schöning published a method that starts with random switch settings and keeps flipping switches that break rules. For 3-SAT, it cut the growth from doubling per switch to multiplying by about 1.33 per switch. That's a big deal when you have hundreds of switches.

Then the progress got very, very small. Painfully small. A later method pushed that number to 1.308. A preprint this year, cited in OpenAI's paper, gets it to 1.307031578. Researchers were fighting over the third decimal place.

The Exponential Time Hypothesis was a bet that this grind would go on forever without ever reaching the finish line. You could keep shaving the number down, but it would stay above 1 for good. Every method, however clever, would still multiply the work by some fixed amount bigger than 1 with each switch you add. The puzzle would stay exponential, period.

Nobody proved this. Hence the name. But almost everyone in the field believed it, and they did something useful with that belief. They used it as a measuring stick. If you could show that solving some other problem quickly would also let you solve 3-SAT quickly, then you'd shown that the other problem was hopeless too, assuming the hypothesis held. OpenAI's announcement puts the count of papers built this way in the hundreds, across graph theory, computational biology, databases and geometry. A lot of what computer science thinks it knows about which problems are hopeless to solve quickly rests on that one assumption. OpenAI's post credits Impagliazzo, Paturi and a third colleague, Francis Zane, as its original proposers.

The hypothesis, usually shortened to ETH, is closely tied to the famous P versus NP problem, one of the Clay Mathematics Institute's Millennium Prize problems, which asks whether every puzzle whose answers are easy to check is also easy to solve. Knocking ETH down doesn't solve P versus NP, and the paper doesn't claim it does. It would mean one of the field's firmest beliefs about hard puzzles was wrong, if the paper holds up.

What the AI claims it found

The paper describes a method for counting every way to satisfy a switch puzzle like this, which also tells you whether there's at least one. Its running time still grows enormously fast as you add switches. But it grows more slowly than any fixed "multiply by a number bigger than 1 per switch" pattern. In the field's language, it's subexponential. If it's right, all that decimal-shaving was beside the point. A completely different approach skipped past the whole contest.

The paper turns the puzzle into a system of equations and counts their shared solutions with heavy algebra, building on earlier tools including one that Impagliazzo, Paturi and Francis Zane published in 2001. The paper is dated October 17, with a revision on October 25, the day before it went public, and it runs 67 pages of dense math, with a reference list that reaches all the way back to Schöning's 1999 paper.

The headline invites a bigger reading than the paper supports. The paper itself states that its result doesn't mean every hard problem now has a fast solution. It does claim faster methods for a few related counting jobs, such as counting the ways to color a network of dots so that no two connected dots share a color. Neither the paper nor OpenAI's announcement mentions encryption at all. OpenAI's post calls it a result that "reopens questions about how much faster these tasks could become" and states plainly that turning it into practical improvements "will require significant further research."

So nobody's phone gets faster this week. What changes, if the proof survives, is the map that computer scientists have spent decades drawing to decide which problems are worth attacking with everything they've got and which ones are better left alone because the hypothesis suggested they were hopeless.

Checked by a computer, not yet by people

OpenAI didn't just post a paper. It also posted a version of the argument written in Lean, a programming language built so that a computer can check a proof line by line. If Lean accepts a proof, the logic holds for the exact statement that was typed in. That's a much higher bar than a human reading a PDF and nodding along.

But a computer check only covers what was typed in. Someone still has to confirm that the typed statement matches the claim in the headline, and that nothing important got lost in translation. OpenAI's own notes for this result show why that step matters. The Lean version proves a slightly looser speed limit than the one in the paper's main theorem. The looser version would still beat the hypothesis, so the headline claim doesn't depend on the gap, but it's the kind of detail human readers exist to catch.

Impagliazzo, Paturi and Williams posted an open letter to their field on Monday, and its second paragraph opens like this: "Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny and an understanding that others can reconstruct, question, and build upon."

Williams posted a short thread on Bluesky around 5:50 p.m. Eastern, about half an hour after the paper was added to OpenAI's public repository. "An internal model at OpenAI has produced a claimed refutation of ETH!" he wrote. The three signed no nondisclosure agreements and aren't being paid, he added, and they asked OpenAI to release all of its raw material on the result and to pay for a conference for the whole research community. OpenAI agreed to both.

Later in the thread, he added a line that captures the odd position academics are in right now: "We do not have access to their internal models. We only got the PDF."

The letter itself is more generous than you might expect from people being told their famous idea is wrong. "If the claim is correct, it will change an important part of theoretical computer science," they wrote. "The ideas, reductions, and techniques developed through that work retain their value, even as some of their interpretations may change. There should be room both for excitement about new possibilities and for thoughtful reassessment of directions many of us have pursued for years."

A month of AI breakthroughs nobody has finished reading

If this were a one-off, it would be a strange and wonderful story. It isn't. That's what makes this fall so unsettling for working mathematicians.

In September, OpenAI announced what Scientific American called the biggest math breakthrough in two decades, a claimed solution to a famous problem about how fluids move, known as Navier-Stokes. The magazine reported that it came from a swarm of 10,000 AI agents and cost millions of dollars in computing. In late September, a panel of well-known mathematicians formed the Advisory Group on Mathematics and AI, after OpenAI approached some of them about an advisory board and they chose to set up an independent group instead, one that takes no payment and publishes its advice to AI companies in the open.

Then, on October 6, OpenAI released 722 math manuscripts on GitHub at once, grouped into 372 families of related results. They included claimed progress on problems tied to the Riemann hypothesis and a claimed new record for how quickly computers can multiply grids of numbers. Scientific American reported that OpenAI's own mathematicians hadn't fully understood many of the results yet. The next day, OpenAI withdrew three manuscripts because of a sign error that broke the argument in one paper and two that depended on it. It revised 14 others. By the company's own count, about 42% of the main results in the collection have been checked in Lean.

Experts who have dug in are impressed and wary at once. New York University mathematician Roland Bauerschmidt told Scientific American that the first paper in one physics-flavored group of results was groundbreaking. About another in the same group, he was less kind. "The second paper is horrible," he told the magazine. "If these results had been sent to me by a nobody, I would have deleted the e-mail."

Monday's release came with two other claims alongside the one about computing. One is a math proof about how waves focus that, if correct, also settles a famous geometry puzzle called the Kakeya conjecture in every dimension. Mathematician Hong Wang won a Fields Medal this summer, one of math's top prizes, for her work with Joshua Zahl settling the three-dimensional version. The other is a physics proof that, among other things, covers part of the Yang-Mills problem, another of the Clay Millennium Prize problems. Monday's announcement doesn't mention claiming a prize. In September, OpenAI stated it wouldn't claim one for its Navier-Stokes work.

Each of the three results is getting a different release plan. The math proof went out raw, for anyone to pick apart, and the computer science proof went public right away at the request of the Impagliazzo, Paturi and Williams group. The physics group, led by Nobel laureate David Gross, chose to hold back the AI's material for now and write the work up themselves.

The fight over who gets to look first

The release plan is its own controversy, and the timing is awkward.

On Sunday, one day before OpenAI's announcement, that same advisory group, which had discussed its earlier recommendations with OpenAI, published a statement on exactly this practice. When an AI company hand-picks experts to receive and explain its results, the group wrote, the drawbacks outweigh the benefits. It listed unequal access, a company effectively deciding for the field who does the work, selection shaped by the company's own networks, and a risk that those experts' names end up vouching for the release. "We recommend that AI companies do not adopt this practice for future releases," it wrote. The statement was careful to say this was no criticism of the mathematicians who had taken on those roles.

OpenAI's announcement doesn't hide the tension. It calls its own approach an experiment and acknowledges that picking the first shepherds "necessarily shapes who gets involved first and creates asymmetry of information." The company also states that it isn't seeking academic credit for anything its models produce, and that the human groups should get the credit for the explanations they write. It also points to a $5 million contribution it recently announced to the Simons Foundation, which will manage the money and award it to workshops and conferences that help researchers understand AI-made results.

Credit is the touchy part. Academic careers run on being the person who solved something. When a company's AI can produce results faster than humans can read them, the slow work of checking and explaining becomes a bigger share of the job, and right now that work doesn't earn much recognition. The ETH letter names the problem directly. "As discoveries come faster, recognition may go mainly to those who publish first or have the most powerful tools, while the work of checking, explaining, and building on results receives less credit," the three researchers wrote.

They also asked a question that applies well beyond computer science: "How can we support students and researchers as methods and research directions change, while preserving the understanding and judgment needed to question results and develop new ideas?"

What happens now

For the next few weeks, the most interesting work in theoretical computer science will be people reading a 67-page PDF very slowly. The group's letter promises a shared space for notes and corrections, plus a blog and a feedback form, both listed as coming in a day or two. The letter asks that the whole effort stay open to independent approaches and criticism, with no company or hand-picked group owning it, the three letter writers included.

If the proof holds, the measuring stick that hundreds of papers relied on is gone, and researchers will have to sort out which of those "too hard to do fast" results still stand on other grounds. If it fails, the October 7 withdrawals show what that looks like in OpenAI's repository: a notice on the paper explaining the gap.

Either way, two of the people who wrote down the hypothesis in 1999 are back at it 27 years later. This time they're reading a proof from a machine. Their letter's appendix lists the place to follow along. It points back to OpenAI's announcement page, which it calls "the authoritative location for the original PDFs, any accompanying source or formalization, and subsequent corrections."

References

1. OpenAI, "Working with academic communities to build scientific understanding," Oct 26, 2026: https://openai.com/index/building-scientific-understanding-with-academic-communities/
2. OpenAI, "The Exponential Time Hypothesis is False" (paper, dated Oct 17, revised Oct 25, 2026), openai/math on GitHub: https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf
3. OpenAI, Lean formalization scope for the ETH paper: https://github.com/openai/math/blob/main/lean/docs/378.md
4. OpenAI, openai/math repository history (Oct 7 withdrawals and fixes, Oct 26 additions): https://github.com/openai/math/blob/main/history.md
5. Russell Impagliazzo, Ramamohan Paturi and Ryan Williams, open letter to the community, Oct 26, 2026: https://docs.google.com/document/d/1adB0IhJgLzsmbfCgoLrtoJTjnlPf74UnyjMo35P5JHo/edit?tab=t.0
6. Ryan Williams on Bluesky, Oct 26, 2026: https://bsky.app/profile/rrwilliams.bsky.social
7. OpenAI, "Sharing AI progress in mathematics," Oct 6, 2026 (updated Oct 15): https://openai.com/index/sharing-ai-progress-in-mathematics/
8. Advisory Group on Mathematics and AI (AGMAI), "Disadvantages of Designating Mathematicians for AI Output Releases," Oct 25, 2026: https://agmai.org/
9. Richard Lawler, The Verge, Oct 26, 2026: https://www.theverge.com/ai-artificial-intelligence/1019143/openai-eth-kaseya-science-math-physics
10. The Next Web, Oct 26, 2026: https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills
11. Joseph Howlett, Scientific American, Oct 6, 2026: https://www.scientificamerican.com/article/openai-unleashes-hundreds-more-math-results-upon-a-field-already-in-shock/
12. Peter Hall and Joseph Howlett, Scientific American, Oct 8, 2026: https://www.scientificamerican.com/article/the-most-exciting-claims-from-openais-heap-of-new-proofs/
13. Robert Hart, The Verge, Oct 6, 2026: https://www.theverge.com/ai-artificial-intelligence/1005004/openai-math-release-github
14. Impagliazzo and Paturi, "Complexity of k-SAT," IEEE Conference on Computational Complexity, 1999: https://doi.org/10.1109/CCC.1999.766282
15. Impagliazzo, Paturi and Zane, "Which Problems Have Strongly Exponential Complexity?," Journal of Computer and System Sciences, 2001: https://doi.org/10.1006/jcss.2001.1774
16. Lean programming language: https://lean-lang.org/