AI might have just changed what we think computers can do

On 26 October, OpenAI claimed its AI models had solved three long-standing problems in mathematics, computer science and physics. Hours later, Anthropic said Claude had independently reached one of the same results. If it holds, an assumption that has shaped computer science for nearly thirty years is wrong, and we're still working out what follows.

The announcement was extraordinary.

OpenAI said its models had produced solutions to problems that have resisted researchers for decades. One sits in the mathematics of waves and geometry, another in the foundations of quantum field theory. The third, and the one I keep coming back to, challenges something computer scientists have believed since the late 1990s about how quickly certain problems can be solved.

If that result holds up, some problems we've spent decades treating as fundamentally difficult may be easier than we thought. Nobody has invented a faster chip here. The theory describing what computers can efficiently calculate may simply have been wrong, which is a much bigger development than the next generation of processors.

Some problems get difficult very quickly

Take a scheduling system. You've got fifty employees and hundreds of tasks, plus skills, availability and rules about who can work with whom, and you want a schedule that satisfies every requirement.

With a handful of people that's straightforward. Add more people and constraints and the number of possible combinations grows enormously.

Computer scientists sort problems by how their workload grows as the input gets bigger. An algorithm that takes twice as long when you double the input is usually manageable. One whose workload doubles every time you add a single variable is a different proposition altogether.

Picture a problem with a hundred yes-or-no variables. There are 2¹⁰⁰ possible combinations, more than a nonillion, and you obviously don't want to check them one by one.

Modern solvers don't have to. Clever algorithms rule out huge numbers of possibilities without examining each individually. The open question is how much better those algorithms can get, and for decades researchers have suspected there's a hard limit. The most influential statement of that limit is the Exponential Time Hypothesis.

The assumption we've relied on since the 1990s

Russell Impagliazzo and Ramamohan Paturi proposed the Exponential Time Hypothesis, or ETH, in the late 1990s. It concerns Boolean satisfiability (SAT), which asks whether you can assign true or false values to a set of variables so that a collection of logical conditions all hold.

SAT sounds simple. It's also one of the foundational problems in complexity theory, with practical uses in hardware verification, software analysis and automated reasoning.

Roughly speaking, ETH says certain forms of SAT can't be solved in subexponential time in the worst case. In other words, there's a floor under how far clever algorithms can tame the explosive growth. Researchers have leaned on it in hundreds of papers to set limits on algorithms in graph theory, databases, computational biology and elsewhere. Those limits are conditional and hold only as long as ETH does.

On 26 October, OpenAI said its model had found a proof that ETH is false. The company dates the result to 16 October and says it was formalised the next day in Lean, a system that checks mathematical proofs by machine.

It wasn't alone. A few hours later, Anthropic published its own paper saying an internal Claude model had independently found a similar algorithm on the same day, also backed by a Lean proof. Two labs arriving separately at the same answer is a strong signal, though the expert review still has to run its course.

Impagliazzo and Paturi are leading that review themselves, with MIT's Ryan Williams. They've been clear that taking part isn't an endorsement and that a claim this significant needs careful, independent scrutiny. If it stands, a foundational assumption about computational difficulty will need rethinking.

Does this mean we can solve impossible problems?

No, and this is where some headlines will run ahead of the science.

Disproving ETH doesn't prove every hard problem can be solved efficiently. It doesn't settle P versus NP either, and it certainly won't make your scheduling software a million times faster next Tuesday.

Proving that an algorithm with certain theoretical properties exists is a long way from shipping something that runs well on real hardware. A subexponential algorithm can still be astronomically slow, or carry so much overhead that it never beats existing approaches at the problem sizes businesses deal with.

Developers meet a small version of this all the time. The algorithm with the better theoretical complexity often loses on today's data, as the simpler option uses memory well and plays nicely with the processor.

So the significance here has little to do with speed. A limit we thought might be fundamental may turn out to be nothing of the sort, and once you know a barrier isn't absolute, you've got a reason to look for routes around it.

Why it matters for software

A surprising amount of computing comes down to choosing between huge numbers of possible combinations. Logistics is full of it, from delivery routing to spreading work across warehouses. Chip designers use sophisticated algorithms to check that ever more complicated circuits behave correctly, and the same kind of problem turns up in automated planning, database processing and software verification tools.

None of these is identical to SAT, and the new result doesn't hand any of them a faster solution. Complexity theory does tell us which problems are related, though, and how progress in one area can carry into others.

Some existing arguments about computational hardness depend on ETH being true. If it's false, those arguments no longer establish the limits researchers thought they did. Parts of the theoretical map need redrawing, and a new map may show routes to better algorithms that looked impossible before.

That's the part I'll be watching. Can researchers turn the new mathematics into practical algorithms over the next few years?

The other two results matter too

The computer science claim has grabbed the headlines. The other two deserve a look as well.

The first sits in harmonic analysis, the branch of mathematics that breaks complicated signals and functions into simpler components. OpenAI says its models proved the local smoothing conjecture for the Euclidean wave equation in every dimension, which would also settle the Kakeya conjecture and Stein's restriction conjecture. Fourier analysis, one of the field's central tools, underpins digital signal processing, audio compression and medical imaging.

I wouldn't expect a better audio codec from this proof. The journey from a theoretical result to a commercial product is long, and sometimes it never arrives. Better understanding of waves and high-dimensional structures does tend to feed, eventually, into how we model physical systems and build computational methods.

The second concerns quantum field theory. OpenAI claims its models produced rigorous proofs that certain interacting quantum field theories exist in four dimensions, including quantum chromodynamics, which describes the strong nuclear force. The work touches on the Yang-Mills existence problem, one of the Millennium Prize Problems.

For now, this is the hardest of the three to check. The physics review group, led by Nobel laureate David Gross, has chosen to hold back the AI-produced material and write up the work itself.

It's fundamental physics, and it won't fix the engineering problems of building reliable quantum processors. It could shape theoretical research and future computational techniques. The important word there is could.

The bigger breakthrough might be the AI

For me, the most interesting part of all this is how the results were produced.

We've talked for years about AI writing code and summarising research. Useful, all of it, and mostly a matter of applying knowledge we already have. Here, AI systems are proposing solutions to research problems that have defeated some of the best mathematicians alive, and expressing those results in a form a machine can check.

Lean is a proof assistant with a small trusted kernel that checks whether each step of a formal derivation follows its rules. It gives researchers a far stronger foundation than another language model reading a proof and deciding it sounds convincing.

Some risk remains. The formal statement still has to say what the mathematicians meant, and there's already a cautionary example: a recent preprint argued that the Lean version of OpenAI's earlier Navier-Stokes work didn't match the natural-language proof it was meant to capture. The checker itself also has to be trustworthy.

Software engineering has a parallel. We already have AI generating code, with tests and type checkers helping establish whether it behaves. Formal verification goes further, expressing properties mathematically and proving them, where tests can only sample a handful of scenarios.

Imagine tools that produce both the implementation and a machine-checkable argument that its important properties hold. For safety-critical software, security-sensitive systems and complex infrastructure, that would be a big deal. Formally verifying every website and business application is a long way off. The cost of more rigorous verification could still fall sharply, and that would shift what counts as reasonable engineering practice.

It changes the economics of research

Mathematical research has always been limited by how many people have the expertise and time to attack hard problems. Computers have helped enormously, yet the creative work has stayed largely human.

If AI can contribute meaningfully to new proofs, the economics of discovery shift. Researchers could explore more possibilities, try unusual approaches and look at questions that previously got little attention.

Human mathematicians still decide which questions are worth asking. They interpret results and catch errors.

Volume is the catch. OpenAI published 722 maths manuscripts on 6 October alone, far more than the community can referee quickly, so checking has become the bottleneck. When the ETH reviewers agreed to take part, they asked OpenAI to release all its raw data on the result and to fund a conference for the research community. OpenAI agreed to both.

Finding an answer and understanding why it matters are separate jobs. The value comes from turning the important results into knowledge other researchers and engineers can use.

What this means for developers today

If you're building business applications, APIs or integrations, very little changes tomorrow morning. You still need to understand your data and test your assumptions.

Plenty of commerce systems already live with combinatorial problems. A promotions engine working out the best combination of stacked offers in a basket is one. Allocating picks across warehouse bays is another. Nothing about either changes this year, and I wouldn't rewrite a scheduling engine on the strength of a complexity theory announcement.

The direction of travel is worth noticing, though. AI is moving from implementing known solutions towards helping find new ones. One day, asking an AI to optimise a complex system might mean it discovers a more efficient algorithm or proves a particular approach works, which goes well beyond rewriting a loop or adding a database index.

The first applications will probably be in research and specialist engineering. Improvements at that level tend to work their way into everyday tools. Most developers never think about complexity theory, yet they benefit daily from decades of research into compilers, database engines, encryption and optimisation. More of the next round of those improvements may come from AI-assisted mathematical discovery.

We may need to rethink what computers can do

Some proportion is in order. Three announcements don't mean every long-standing problem is solved, and the research community still has to examine these results and work out their scope.

Dismissing them as academic curiosities would be a mistake, all the same. Computing is built on mathematics, and when that foundation shifts, what computers can do shifts with it.

There's something striking about AI challenging a long-held assumption about the limits of computation. We've spent years throwing more computing power at AI. Now AI is helping us understand what computation itself can achieve.

How much of that turns into practical technology is anyone's guess. If the results hold up, the next few years of computer science research will be very interesting indeed.

Sources and further reading

• OpenAI — Working with academic communities to build scientific understanding (26 October 2026)
• OpenAI — Sharing AI progress in mathematics (6 October 2026)
• OpenAI — On the Navier–Stokes Millennium Prize Problem (8 September 2026)
• Nature — OpenAI claims huge maths breakthrough on a famed Millennium Problem
• Plus Maths — Artificial intelligence and mathematical proof