AI disproves a 27-year-old computer science conjecture, but experts haven't ruled yet

What happened

In late October, OpenAI claimed that an internal AI model had disproved the Exponential Time Hypothesis (ETH). The 27-year-old conjecture underpins hundreds of papers in theoretical computer science. The 67-page paper has a blunt title: "The Exponential Time Hypothesis is False." A day later, Anthropic followed with its own independent counterproof. Both companies verified their proofs in Lean, a program that checks mathematical proofs line by line for logical errors. The papers and formalizations are public on GitHub.

Almost two weeks later, though, the experts still haven't delivered the verdict that matters. According to shiftdelete.net, the three researchers leading the review haven't committed either way. One of them is Russell Impagliazzo, who co-proposed the conjecture in 1999. He called the news a "shock" in an interview with The New York Times.

What the Exponential Time Hypothesis says

The ETH comes from Russell Impagliazzo and Ramamohan Paturi, both at UC San Diego, together with Francis Zane. It's about 3-SAT, a classic logic puzzle. You have many yes/no switches and rules that each link three of them. The goal is to find switch settings that satisfy every rule at once. Checking a proposed answer is easy. Finding one is hard, because every extra switch doubles the number of possible combinations.

The ETH says there's no significant shortcut. In the worst case, any algorithm needs running time that grows exponentially with the number of variables, so roughly like trying every possibility. Researchers treated the ETH like a load-bearing wall. According to OpenAI, hundreds of papers in graph theory, computational biology, databases and geometry rely on it to show that certain problems can't be solved quickly. If the wall falls, those lower bounds, proofs of the form "you can't do better than X," start to wobble.

What exactly OpenAI and Anthropic claim

OpenAI describes a deterministic algorithm, meaning it doesn't use randomness. It counts every satisfying assignment of a k-CNF formula, a generalization of 3-SAT, in subexponential time: the effort grows more slowly than any exponential function. It also needs only a polynomial amount of memory. Counting solutions is at least as hard as asking whether any solution exists, so this would also break the ETH bound for 3-SAT. According to Yahoo/BeInCrypto, the algorithm needs roughly 2^(n/√log n) steps for n variables.

Here's the timeline according to OpenAI:

Anthropic credits its paper to Claude. According to the accompanying repository, an internal research version found the algorithm. The repository also notes that the result is only about asymptotic behavior, not about solving formulas faster in practice.

OpenAI announced two more breakthroughs the same day. According to The Next Web, its models proved Christopher Sogge's 1991 local smoothing conjecture in all dimensions. That would also settle the Kakeya and Stein restriction conjectures. In physics, OpenAI says it rigorously showed that certain quantum field theories exist in four dimensions, including pure Yang-Mills theory. That's part of one of the Clay Mathematics Institute's Millennium Prize Problems. A group led by Nobel laureate David Gross is reviewing this work. It plans to hold off on publishing the AI material and write up the work itself.

Where the review stands

The review is only partly done. Volunteers have rerun both labs' Lean proofs through independent checkers. But according to shiftdelete, neither lab had formalized the step that carries the result from its own machine model over to a standard one. A machine model is the precise mathematical definition of what counts as a "computation step." Outside researchers closed that gap in Lean between November 2 and 5.

What's still open is the human part. Impagliazzo, Paturi and Ryan Williams of MIT are organizing a public review. They have to agree on whether the formal definitions really match the textbook version of the ETH. They also need to check the sharper bound in OpenAI's paper, which wasn't fully formalized. In an open letter, the three make their position clear:

"Our involvement should not be taken as an endorsement of the claim. A result of this magnitude demands careful, independent scrutiny."

Williams says the reviewers aren't being paid and haven't signed any nondisclosure agreements. At their request, OpenAI has agreed to release all raw data behind the ETH result and to fund an academic conference. Impagliazzo told Science: "For me, it's not 100 percent certain." Most researchers had expected stronger variants of the hypothesis to fall first. Computer scientist Scott Aaronson wrote on his blog that his students had come into his office to tell him an OpenAI model had disproved the ETH.

Will computers get faster, and is encryption at risk?

Not anytime soon. The ETH is an asymptotic statement, meaning it's about behavior on arbitrarily large inputs. So a disproof only has to do better on unimaginably large problems. Outside estimates suggest the advantage of OpenAI's verified bound only kicks in at around 10 to the power of 2,389 variables. A problem that size could never be stored. Nothing changes for SAT solvers in chip design or logistics. OpenAI itself writes that a lot more research is needed to find useful algorithms and turn the theory into practical gains. The New York Times was more upbeat in its headline, saying the result could "one day" speed up chip design and break encryption. That's a distant possibility, not a consequence of the current proof.

It also matters what this doesn't touch: P vs. NP. That big open question asks whether every problem whose solution can be checked quickly can also be solved quickly. The ETH was a stronger claim than P ≠ NP, so disproving it leaves the big question open. OpenAI president Greg Brockman wrote shortly after the announcement: "P is probably still not equal to NP." Yahoo/BeInCrypto put it vividly: the AI found a shorter path over the ridge, not a tunnel through the mountain. Bitcoin signatures rely on elliptic curve cryptography, a problem the algorithm doesn't address at all. The acronym caused some amusement too: users on X joked about a "$ETH" crash, even though the conjecture has nothing to do with Ethereum.

Who gets the credit?

OpenAI says it isn't claiming scientific credit. That should go to the researchers who explain and write up the results. The company also gave $5 million to the Simons Foundation for workshops and conferences that review and build on AI results. Even so, Impagliazzo, Paturi and Williams ask in their letter how credit should work when AI finds things first. They worry that recognition will go to whoever publishes first or has the most powerful tools, while checking and explaining get short shrift. Mathematicians raised similar concerns in June in the Leiden Declaration. According to KuCoin, the sheer volume is another warning sign: of 722 math manuscripts OpenAI posted to GitHub in early October, only 162 contained a computer-verified main result.

Our take

If the proofs hold up, this would be one of the most significant results ever credited to an AI. The fact that two labs independently reached a disproof makes the claim more credible. For now, nothing changes in practice for software or encryption. For research, though, it's a turning point, because many hardness proofs will need new foundations. The question everything hinges on is still open: is Lean actually checking the right statement? A machine-verified proof is only as good as the formal statement it's given, and that's exactly what the experts are now examining. Then there's the business side. For OpenAI and Anthropic, math breakthroughs showcase their reasoning models in a fierce race for investor money. OpenAI just closed a funding round at a reported valuation of $1.25 trillion. Whether the announcement becomes an established result won't be clear until the reviewers deliver their verdict.