OpenAI and Anthropic Claim AI Has Disproved a 27-Year-Old Computer Science Hypothesis

In two weeks, a paper by Peter Jonsson, a computer scientist at Linköping University in Sweden, is scheduled to be presented at a conference that WIRED describes as one of the most respected events in theoretical computer science. But as of Monday, Jonsson told WIRED, much of his work was already "dead." OpenAI and Anthropic both say that an AI model has disproved a 27-year-old assumption that supports half of his paper. Both companies also say their models discovered the idea independently on the same day, October 16.

WIRED used the word "irrelevant" in quotation marks in its headline, referring to decades of computer science research. I am not an expert in complexity theory, so I read both papers, the reviewers' open letter, and comments from researchers whose work could be affected. My conclusion is that the result is probably real, could change what researchers understand about difficult problems, but will not make any computer program you use run faster.

The puzzle and the bet

Imagine a row of light switches. Each switch can be on or off, and you have a list of rules. Every rule mentions three switches. For example, one rule might say that switch 1 must be on, switch 4 must be off, or switch 9 must be on. The rule is satisfied if at least one of these statements is true. The question is whether there is any way to set all the switches so that every rule is satisfied. Computer scientists call this problem 3-SAT, short for satisfiability. Checking a suggested arrangement is easy: you simply go through the rules one by one. Finding a correct arrangement is much harder. Five switches have 32 possible arrangements, and every new switch doubles the number. Ten switches have about a thousand arrangements, while 50 have about a quadrillion.

Trying every possible arrangement is called brute force. With this method, every new switch doubles the amount of work. Computer scientists have found much better methods since the 1980s. According to Anthropic's paper, the best methods known before this month reduced the multiplier to about 1.3. The best deterministic method had a multiplier of 1.328, while the best randomized method had a multiplier of 1.308. This saves a lot of work, but the basic pattern stays the same: every new switch still increases the amount of work by some fixed amount.

In 1999, Russell Impagliazzo and Ramamohan Paturi of UC San Diego, together with Francis Zane, suggested that this would always be true. No matter how clever a method became, they argued, each new switch would increase the amount of work by at least some fixed amount greater than one. They called this the exponential time hypothesis, or ETH. For 27 years, it was a widely accepted idea that nobody had proved. It is related to the better-known P-versus-NP question, which asks whether problems that are easy to check are also easy to solve. Here, "easy" means that the amount of work grows steadily as a problem gets bigger, rather than doubling at each step. ETH makes a much stronger claim. It says that the multiplier can never fall below a certain limit. There is a large gap between this claim and the P-versus-NP question.

This strong assumption became a useful tool. Imagine you are studying another problem, such as creating an exam schedule where no student has two exams at the same time. If you can show that a fast solution to your scheduling problem would also provide a fast solution to the switch puzzle, then your problem cannot have a fast solution either, provided ETH is true. Researchers have used this approach many times in graph theory, databases, computational biology, and geometry. Anthropic says a search of scientific papers using Claude found more than 800 papers containing at least one result that depends only on ETH or on an even stronger assumption that implies ETH. Jonsson's paper includes such a result. It has two parts: an algorithm, which is a new way to solve his problem, and a proof that no method can do much better. The second part works only if ETH is true.

What the labs claim, and how far to trust it

Both companies say an AI model found a way to get below the limit on October 16. OpenAI's paper is 67 pages long and is titled The Exponential Time Hypothesis is False. Anthropic's paper is 49 pages long, and its author is listed as "Claude, Anthropic." Anthropic says its model discovered the main algorithm without human help, producing 14 million tokens of output. Tokens are the small pieces of text that AI models generate. Anthropic's researchers then worked with Claude to improve how the result was explained. Both papers say their algorithms make the amount of work added by each new switch keep getting smaller and closer to one as the puzzle grows. This is exactly what ETH says cannot happen. Both methods also count every arrangement that works, which is harder than simply finding one working arrangement. According to Anthropic, the two companies reached their results independently. Their papers use different main mathematical approaches but claim almost the same speed.

I usually approach announcements from AI companies with doubt. What caught my attention here was the group checking the work. OpenAI's own announcement says its result will be checked and guided by a group led by Impagliazzo, Paturi, and Ryan Williams of MIT. Two of these three researchers originally proposed ETH. At their request, OpenAI agreed to publish all its raw data so that researchers around the world can check the result independently. The group's open letter, which discusses OpenAI's claim, also includes a link to Anthropic's result for anyone who wants to examine that work.

Both companies say they checked their proofs using Lean, a computer program that checks mathematical proofs one step at a time and rejects steps that do not follow logically. Anthropic says its proof uses only Lean's three standard axioms, meaning it does not introduce any additional basic assumptions. It also says a second checker, written independently, checked the proof again. But Lean has a limitation. As I explained when OpenAI released 722 mathematical papers earlier this month, Lean checks whether a proof correctly follows from the statement it is given. A person still needs to check that the statement actually matches what the paper claims. Anthropic's notes clearly acknowledge this: "no machine checks that this file says what the paper says." OpenAI's notes also explain that its Lean file proves a slightly slower result than the main number in its paper, although it is still strong enough to disprove ETH.

The reviewers' letter warns that their involvement "should not be taken as certification of the claim." Williams told TechCrunch that some parts of OpenAI's proof seemed straightforward, but "two or three alien-looking parts" made him think the entire research community needed to examine it together. As of October 29, I have not found any reports identifying a mistake in either proof. The researchers most qualified to find such mistakes are still examining the work.

Where it stands, October 29, 2026

• Claimed: OpenAI and Anthropic each say an AI model discovered an algorithm for 3-SAT that runs in 2^o(n) time on October 16. If correct, this would disprove ETH.
• Checked by machine: Both proofs have been checked using Lean. People still need to confirm that each Lean statement matches the claims in its paper. OpenAI's Lean file proves a slightly weaker result than its paper claims.
• Under review: Impagliazzo, Paturi, and Williams are organizing a wider examination of OpenAI's claim. They have made clear that their involvement does not mean they have officially confirmed it.
• Practical impact: Anthropic's paper says the result "says nothing about solving formulas in practice."

Faster, eventually

On page two of Anthropic's paper, the authors consider 3-SAT puzzles with five rules for every switch. They explain that their method would not be better than brute force unless the puzzle had more than 10^10,000 switches. That is a 1 followed by 10,000 zeros. They also say their general approach is unlikely to offer any general improvement for puzzles with fewer than about 10 million switches, no matter how it is designed. Brute force is already impossible to use in practice with just 100 switches. The number 10^10,000 is enormously larger than the number of atoms in the observable universe, which is roughly a 1 followed by 80 zeros. The paper therefore concludes that the result "says nothing about solving formulas in practice."

But in the mathematical sense that ETH is concerned with, the new method would still be faster eventually. That is because ETH is about how the amount of work grows when puzzles become as large as we can imagine, without any upper limit. Computer scientists call this a galactic algorithm. It is an algorithm that only becomes faster than other methods when the input is so large that it could never actually exist. Williams also doubts that this is the best possible algorithm of this kind. He told TechCrunch that he does not think OpenAI's algorithm "could possibly be the best algorithm you can get."

Encryption depends on a similar assumption to ETH: that certain problems take too long to solve to be practical. Williams told TechCrunch that one of his first questions to OpenAI's science lead was whether the result had broken any encryption systems. He says the team had apparently checked and was "reasonably confident" that it had not. Daniel Lokshtanov of UC Santa Barbara told WIRED that the result does not directly affect cryptography but "should definitely scare some cryptosystem designers." On October 29, a research paper credited to researchers at Ruhr University Bochum and the Max Planck Institute for Security and Privacy examined this exact issue. I could not independently confirm who wrote it beyond the names printed on the paper. Assuming OpenAI's algorithm is correct, the authors apply it to elliptic curves, a type of mathematics used in many modern encryption systems. Their calculations show that an attack on these curves could take slightly less than exponential time. The authors call this slightly subexponential time. However, the improvement only appears with unbelievably large numbers, and they say it "does not imply improved concrete attacks on currently deployed elliptic curves."

TechCrunch made a bigger claim than either AI company, suggesting that this result might open a path toward P equals NP. This is the possibility that problems which seem difficult to solve might actually have easy solutions. Anthropic's paper says the new result does not directly answer that question. OpenAI's paper also says its faster algorithm cannot be applied to NP problems in general. The claimed method concerns a large area of mathematics between problems that are easy to solve and the minimum limit described by ETH. Williams said computer scientists should probably give a little more consideration to the possibility that P equals NP. But he added that "one's weight may vary."

Online discussions went even further. People claimed that AI had proved P equals NP, that it would burst the AI bubble, or that the encryption used by every bank would suddenly stop working. One person joked about collecting the million-dollar prize because P equals NP only when N equals one. But P and NP are two groups of problems: those that are easy to solve and those that are easy to check. There is no division involved. The joke does point to a real misunderstanding, though. Even a genuine proof that P equals NP would not automatically break bank security or burst an AI investment bubble. A mathematical proof can show that an easy method exists without actually giving us that method. And even a method that researchers have written down, like the two published this week, might only work on impossibly large problems.

Who it lands on

If the proofs are correct, the many results that rely on ETH to show that certain problems are difficult will lose their foundation. The strong exponential time hypothesis, which is an even stronger version of ETH, would also be affected. However, Anthropic's paper says the result does not disprove a weaker assumption called the orthogonal vectors hypothesis. Many proofs of lower limits on computing time in fine-grained complexity theory depend on this assumption, so some parts of the field remain unaffected.

The researchers most affected are those who built their work on ETH. Lokshtanov told WIRED that if the result is confirmed, he will be "galactically wrong," and around 50 of his published papers will become "pointless" or need to be reconsidered. He described the result as "a giant bomb dropped into the middle of the field" and said it was "really cool and terrible at the same time." Thore Husfeldt, who leads the algorithms research group at the IT University of Copenhagen, had spent most of this year working on a single problem. "As far as I can tell, it's now all irrelevant," he said. He told WIRED that AI research results are now arriving every week or two and destroying projects that researchers are still working on. His department has even considered hiring an occupational psychologist because "some people are really depressed and really sad."

WIRED also reports that researchers are struggling to deal with the amount of material being produced by AI. During his interview with WIRED, Husfeldt received a 17-page paper about the consequences of this very result. He suspects it was written by AI and sent from a random Gmail account. He does not plan to read it. "Reading math is a very big investment of cognitive time," he said.

"Irrelevant" and "pointless" are words the researchers themselves used. But as I understand it, what they mainly stand to lose is a conclusion. Every paper in Anthropic's count has at least one result that is only true if ETH, or a stronger assumption that implies ETH, is true. A statement such as if ETH holds, then this problem is hard is still logically correct. But if the new proofs are confirmed, ETH is false. That means these statements can no longer be used to show that the problems are difficult. The reviewers' letter offers this careful reassurance: the ideas, reductions, and methods developed using ETH "retain their value, even as some of their interpretations may change." Jonsson's paper shows the difference clearly. The part containing his algorithm still works just as well as it did last week. But the part claiming that nobody could find a better method depends on ETH. If ETH is false, that part no longer proves anything.

Husfeldt also described the result as "fantastic." He told WIRED that being a mathematician is like wandering around in a completely dark room. This result is like someone suddenly turning on powerful lights across an entire area of research. Researchers can now see many things they could not see before, and "we just run around like overexcited bunnies" exploring all the new possibilities. Victor Lagerkvist, another researcher at Linköping, plans to return to problems he had given up on because he believed ETH was true. The same result that makes his biggest problem of the year seem irrelevant is also something he considers fantastic.

Jonsson's presentation is still scheduled to take place, although one of his coauthors will give the talk. He expects many presentations at the conference to begin with something like, "ETH is false, half of my paper does not work." He believes his own paper might be saved by using a different method. He also plans to study OpenAI's proof to see what he can learn from it.

If you work anywhere near complexity theory, I'd love to hear what this week has been like. And if I've misunderstood any of the mathematics, please tell me.

Disclosure: I use Claude, made by Anthropic, one of the two companies in this story, to help produce my work.