AI Refutes the Exponential Time Hypothesis: What This All Means

OpenAI and Anthropic each published a proof that the exponential time hypothesis is false.

ETH is a 27-year-old assumption in theoretical computer science that says some problems can never be solved much faster than by brute force. Now, the top AI labs say that's simply not true.

If the proofs hold up, they are the most significant AI-generated result in computer science to date. They also force a rethink of literally hundreds of research papers that assumed ETH to be true.

In this article, we explain what the exponential time hypothesis actually means, along with P vs. NP, which is related. We will also look at what exactly the two labs claim, how the proofs were checked, and what does (and doesn't) change for cryptography.

P vs. NP in Plain Terms

P versus NP asks whether every problem whose answer is easy to check is also easy to solve. It is one of the seven Millennium Prize Problems, and it is still open after this news.

A Sudoku puzzle is the classic illustration. Checking a filled-in grid takes seconds: scan each row, column, and box for repeats. Finding the solution from a blank-ish grid can take far longer, and the gap explodes as the grid grows.

• P is the class of problems a computer can solve in polynomial time, meaning the work grows like n^², n^³, and so on as the input size n grows.
• NP is the class of problems whose proposed solutions a computer can verify in polynomial time.

Every problem in P is also in NP. The open question is whether the reverse holds. Most computer scientists believe P ≠ NP, so that some problems are fundamentally harder to solve than to check. Modern cryptography leans on that belief: encrypting is easy, but undoing encryption without the key should be hard.

What Is the Exponential Time Hypothesis?

ETH is sharper: it claims that one specific NP problem, 3-SAT, needs exponential time no matter how clever the algorithm. Russell Impagliazzo and Ramamohan Paturi of UC San Diego proposed it in the late 1990s, with Francis Zane contributing to the foundational work.

The 3-SAT problem

In 3-SAT, you get a formula made of n true/false variables and a list of clauses. Each clause joins three conditions with OR, for example "x₁ is true OR x₄ is false OR x₇ is true." The task is to find a setting of the variables that satisfies every clause at once.

Brute force tries all 2ⁿ settings, so each extra variable doubles the work. You can see how at around 100 variables that is hopeless.

What ETH says

ETH states that there is some constant c > 1 such that no algorithm solves 3-SAT faster than cⁿ. Clever algorithms can shrink the base below 2, but never all the way down to something subexponential. Formally: there exists δ > 0 such that 3-SAT cannot be solved in time O(2^δn).

For decades, progress matched that picture. Researchers kept shaving the base down, but it stayed well above 1. Because 3-SAT can be converted into many other problems, ETH became a workhorse assumption. Researchers used it to argue that problems like Clique, Vertex Cover, Independent Set, and others can't be solved much faster either. 

How the new result compares

The new bound is written 2^o(n) in shorthand. The cost per added variable shrinks toward 1 as n grows, which is exactly what ETH said was impossible.

What OpenAI and Anthropic Announced

Both labs reached essentially the same subexponential bound independently, and both backed their papers with machine-checked proofs in the Lean proof assistant.

Anthropic says Claude found the core algorithm with no human input after producing about 14 million tokens of output. Its method uses tensor networks and rank arguments. Researchers then helped with the final paper.

Why did both labs find it on the same day?

Neither lab has explained the timing. Anthropic's paper calls the two results independent and concurrent, and the two write-ups take different routes through the math to reach essentially the same bound. 

Some context makes the overlap less surprising than it first looks. Both labs have been pointing their models at long lists of open problems, and OpenAI alone released hundreds of AI-generated math manuscripts in early October. ETH is one of the best-known targets in the field, and both models learned from the same published research. Independent, simultaneous discovery is also an old pattern in science, as with Newton and Leibniz on calculus or Darwin and Wallace on natural selection.

How solid are the proofs?

Lean confirms that a formal statement follows logically from its axioms. It cannot confirm that the formal statement says the same thing as the paper. Anthropic notes that no machine checks this match, and OpenAI says its Lean file proves a slightly weaker bound than its headline.

Now, the same researchers who proposed the problem, Impagliazzo and Paturi, alogn with MIT's Ryan Williams, are organizing workshops to assess whether the formal statements truly capture ETH. Their letter stresses that taking part in the review is not an endorsement. As of now, writing the article, no one had publicly found a flaw. 

Williams has said parts of OpenAI's proof look routine, while "two or three alien-looking parts" still need scrutiny. Impagliazzo, one of ETH's authors, has described the result as deeply surprising.

What Changes and What Doesn't

In practice, almost nothing changes today (phew): the new algorithms only beat brute force on inputs far larger than anything a computer could ever hold.

No faster SAT solvers

Anthropic’s paper says its method only beats brute force on astronomically large inputs. For typical formulas with five clauses per variable, the crossover point is a number with about 10,000 digits. In the most general case, it’s a number with roughly 100 million digits. 

The authors also say their approach is unlikely to help on anything under about 10 million variables. The SAT solvers used in chip verification, scheduling, and planning won't get faster from this result.

Cryptography is not broken

The result does not touch P vs NP. No one is pretending that. OpenAI says it checked whether the algorithm breaks real cryptosystems and is pretty confident it does not. 

Theory gets rewritten

The bigger impact is on research. Hardness results built on ETH or SETH now need a new footing, and some researchers have said years of their own work may need revisiting. Not everything falls, though. Anthropic notes the result does not refute the orthogonal vectors problem, which supports many fine-grained complexity results. 

Why It Matters for AI

The headline is less about 3-SAT and more about who found the answer: two AI systems independently overturned a conjecture that human experts had trusted for a generation.

AI as a research collaborator

Researchers now describe new AI results landing every week or two, disrupting projects already in progress. Formal tools like Lean are becoming central because they let humans trust a long machine-written proof without re-deriving every line.

Hidden shortcuts and self-improvement

ETH captured a belief that some search problems have no clever shortcut. If that belief is wrong, other obviously hard problems may hide shortcuts too.

I'm thinking about algorithm discovery as one area where such shortcuts could matter a lot for recursive self-improvement, which is the idea of AI systems that help design better AI. Using AI to find faster algorithms is one concrete path toward it, though nothing in this result does that directly today.

What it means for data practitioners

For people who build with data, three lessons stand out:

• Complexity theory is not just academic: Knowing why a problem is NP-hard tells you when to think about heuristics, approximations, or solvers instead of exact search.
• Verification is a skill: As AI generates more code and analysis, checking its output (with tests, proofs, or reproducible pipelines) matters as much as producing it.
• Asymptotics can mislead: A "faster" algorithm in theory can be useless at real-world sizes. 

Conclusion

If the proofs survive expert review, the exponential time hypothesis joins the short list of widely believed conjectures that turned out to be false (like Euler’s sum of powers conjecture). But P vs NP remains open and cryptography is safe for now.

The next milestones to watch are the review workshops led by ETH's original authors, independent re-implementations of the algorithms, and whether anyone tightens the bound further.

To build the foundations behind stories like this one, explore our courses on data structures and algorithms, Python programming, and machine learning. They cover the Big-O thinking that makes results like this one readable.