OpenAI and Anthropic say their research models have found ways to solve a famous class of computing problems faster than a long-standing hypothesis predicted. If the results hold up, researchers will have to revisit an assumption used throughout computer science. This is about the time an algorithm needs, not time travel or an instant speed boost for your laptop.
What was the problem?
Imagine scheduling meetings for a group. Each person has constraints: one cannot meet in the morning, another is busy after lunch, and a third needs to meet the first. With a small group, finding a workable schedule is manageable. As the people and conditions multiply, so do the possible combinations.
Computer science has a problem with a similar flavor: can we assign values to variables so that a collection of logical conditions all hold at once? One version is called 3-SAT. A proposed solution is relatively easy to check, but finding one - or proving none exists - can be difficult for some sets of conditions.
If we try every possible assignment, each new variable doubles the number of combinations. Researchers have already devised methods better than this exhaustive search. The deeper question is whether an algorithm can solve every instance with a worst-case running time that grows substantially slower than an exponential function as the number of variables increases.
The exponential time hypothesis, or ETH, says there is no such algorithm for 3-SAT. It is not a proven law. It is an influential assumption that researchers have used to reason about the difficulty of many other problems.
What did the labs propose?
OpenAI says its system found a refutation of ETH and has released both a written proof and a formal version. Shortly afterward, Anthropic published work in which a research model of Claude also proposes an algorithm that contradicts the hypothesis.
Both works describe algorithms with what researchers call subexponential running time. Put simply, as the number of variables becomes sufficiently large, their theoretical running-time bounds grow more slowly than the exponential bound assumed by ETH. That does not mean the calculations become easy or finish in seconds.
Anthropic makes an important qualification: its result concerns how the algorithm scales for very large problems and does not establish how fast it will be in practice. A result can be significant for theory without immediately producing a useful tool for an ordinary computer.
Has AI settled the question?
The companies describe proofs checked with Lean, a program for formally checking mathematical reasoning. Lean helps verify whether conclusions follow from the statements and rules written into a formal proof.
People still have work to do: checking that the formal statement captures the original problem, understanding the ideas and assessing their consequences. OpenAI has brought in outside experts, including researchers who proposed the hypothesis. Anthropic also notes that a person must check whether its formal statement matches the paper.
If the conclusions hold, researchers will need to revisit results that rely specifically on ETH. That does not automatically make every such result false: each one needs to be examined to see what depended on the hypothesis and whether it can be supported another way.
What about passwords and other hard problems?
Refuting ETH does not show that every difficult problem can be solved quickly. Nor does it settle the famous P versus NP question: whether every problem whose answer is easy to check can also be solved quickly.
We should not conclude that everyday encryption has been broken, either. OpenAI says that finding practical algorithms and turning theoretical advances into practical improvements will require further research.
The broader story is that AI is playing a growing role in fundamental research. There is still a long way between a striking claim and an understood, independently examined discovery: people need to unpack the proof, discuss it with other researchers and establish what it actually changes.