Imagine a puzzle with a hundred switches. Every switch must be either on or off, and dozens of rules determine which combinations are allowed. You can check a proposed solution quickly. Finding one — or proving none exists — can be much harder.

Now imagine an artificial intelligence discovering a way to tackle a whole family of these puzzles faster than generations of computer scientists thought possible.

That is the remarkable claim at the center of a debate unfolding this week. On October 26 and 27, 2026, OpenAI and Anthropic published AI-generated research challenging a 27-year-old assumption about the limits of computation. The research is public, parts have been checked using mathematical proof software, and experts are investigating what it really means. OpenAI announcement · Anthropic research release

The hypothesis that shaped 27 years of research

The Exponential Time Hypothesis, or ETH, was proposed in 1999. It concerns a mathematical puzzle called 3-SAT: given a set of logical rules involving true-or-false variables, can you choose values that satisfy all the rules at once?

Suppose you have 30 switches. There are more than a billion possible on-off combinations. Clever algorithms can avoid checking every possibility, but the underlying challenge grows dramatically as more variables are added.

ETH makes a precise prediction: in the worst case, there is no algorithm that solves every 3-SAT problem with a subexponential running time in the number of variables. It does not say that every algorithm must literally inspect all 2^n combinations.

Computer scientists have used this assumption to work out why problems in fields such as graph theory, databases and computational biology may resist dramatically faster algorithms. The hypothesis has served as a foundation for hundreds of conditional research results. OpenAI research note

Two AI labs, one startling conclusion

On October 26, OpenAI announced that one of its internal AI systems had produced a mathematical argument against ETH. According to the company, the natural-language result was found on October 16 and formalized in the proof assistant Lean on October 17. Its paper describes an algorithm that counts satisfying assignments of certain logical formulas in subexponential time. OpenAI’s paper

Anthropic then released a separate result attributed to an internal Claude research model. Its paper, A 2^{o(n)} Time Algorithm for 3-SAT, also claims a subexponential algorithm, including the harder task of counting solutions rather than merely deciding whether one exists. The company published its paper and Lean formalization in a public repository. Anthropic’s technical release

The timing turned the announcement into an unusual scientific moment: two major AI laboratories independently presented results against the same deeply established hypothesis in a matter of hours. Their claims are significant, but publication is not the same as a completed independent scientific evaluation. TechCrunch’s reporting

What does it mean for an AI to prove something?

The word proof has an unusually strict meaning in mathematics. A valid proof must follow logically from its assumptions and definitions, with no missing step.

Lean is software that checks a proof written in a formal mathematical language. It can detect logical gaps that may be difficult for humans to notice in a long argument. Both labs have made formal proof materials available. That is stronger evidence than simply asking a chatbot for an explanation.

But a formal checker cannot, by itself, answer every scientific question. Researchers still need to verify that the formal statements express the intended real-world mathematical claim, that definitions match accepted usage, and that the result’s consequences are correctly understood. Anthropic explicitly points out that Lean does not automatically check that its formal statement says exactly what the paper says. Anthropic’s explanation

There is also a useful technical distinction: OpenAI’s public documentation says its Lean formalization proves a slightly weaker running-time bound than the sharper one in its manuscript. Crucially, the formalized bound is still subexponential — the feature that would challenge ETH. This distinction is precisely why publishing the details matters. OpenAI formalization scope

Does this mean passwords are broken — or that P equals NP?

No. Neither conclusion follows from these announcements.

ETH is related to the famous P versus NP question, which asks, roughly, whether every problem whose solution can be checked efficiently can also be solved efficiently. Refuting ETH would not, on its own, establish P = NP.

And subexponential does not mean instant. An algorithm can improve the theoretical growth rate of its running time while remaining far too slow or complicated for practical use. Anthropic specifically cautions that its result is asymptotic and makes no claim about how well it solves real puzzles today.

There is no demonstrated universal password-breaking method in these papers. The immediate importance is about our understanding of computational limits, not a switch that suddenly makes existing encryption useless. Anthropic release · TechCrunch interview with computer scientist Ryan Williams

The controversy is about science itself

The mathematical claims are only half the story. Researchers are also arguing about how AI-generated discoveries should be released and independently examined.

OpenAI says it is working with independent experts to help translate the new mathematics into understanding that the wider community can evaluate. For the ETH result, a group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams is coordinating that effort. Impagliazzo and Paturi helped introduce ETH, making their involvement especially notable. The company says the group requested public access to the research materials and support for a conference. OpenAI statement

Some researchers welcome that coordination; others worry that allowing a company to choose who sees or interprets breakthroughs first gives a private laboratory too much influence over public knowledge. The debate is about access, credit, scrutiny, and what it means to understand a result that an AI may have found faster than people can explain it. The Verge, October 27

The real question is bigger than one theorem

As of October 28, 2026, the public research materials warrant serious attention, but independent expert assessment is still developing. It would be premature to treat every implication as settled or claim that today’s computers have suddenly become radically faster.

What makes this extraordinary is the possibility that AI is moving from helping scientists search for answers to proposing new mathematics at the frontier of knowledge. That creates an unexpected challenge: humans may have to invent better ways to verify, interpret and share discoveries arriving faster than researchers can absorb them.

If an AI produces a correct proof that very few people can yet explain, has science finished the discovery — or only begun to understand it?

Sources