Solving these 5 maths problems would actually change everything

What if AI does solve all the maths out there? What's the impact for everyday life?

On Monday, OpenAI said one of its internal models had disproved the Exponential Time Hypothesis.

If you're not a computer scientist, that sentence means nothing to you, so here's the short version. The Exponential Time Hypothesis (ETH, to its friends, though sadly unrelated to Ethereum) says that the most basic hard problem in computing, satisfiability, really does need exponential time to solve.

In other words, it says the faster method doesn't exist, as opposed to merely not having been found yet. Hundreds of papers rest on it, in the sense that they prove "X is hard, assuming ETH". Russell Impagliazzo and Mohan Paturi proposed it in 2001, and they are now part of the group checking whether OpenAI's model has just knocked it over.

Some (unrelated) mathematicians are up in arms about it and are unionising to declare that AI maths isn't real human grain-fed maths, as if the field belonged to them rather than to humanity. This is silly, because much like many other fields AI is pointed at, solving obscure maths can have huge benefits to society, beyond keeping mathematicians employed.

Obviously I'm not in that camp. Let's solve all the maths as quickly as we can, and reap the benefits.

Which raises an obvious question: which problems should we actually want AI to knock over next?

Mostly not the famous ones.

Here are my five, with a rule for each: what changes if the answer is yes, and what changes if the answer is no. For most of them, one of those two is a revolution and the other is a shrug. That asymmetry is most of the story.

1. Can attention be computed faster than quadratically?

Every large language model runs on attention: for every token in the context, the model looks at every other token. That's n squared work for a context of n tokens, which is why a million-token context costs a fortune and why your chatbot gets slow when the conversation gets long.

In 2023, Josh Alman and Zhao Song proved that you can't do better. Or rather: you can't do better assuming a conjecture called the Strong Exponential Time Hypothesis (SETH), which is ETH's bigger, bolder brother. SETH implies ETH. Which means that if OpenAI's refutation of ETH holds up, SETH is dead too, and the theorem that said "don't bother looking for sub-quadratic attention" has just lost its premise.

This does not hand anyone the solution. What's gone is one important theoretical barrier, a reason to not bother looking. And given how much AI firepower we already have at our disposal, and how much economic return such a solution would have... people are going to start looking harder.

If yes: long context stops costing quadratically. Everything that currently runs at "whole codebase" or "whole legal case" scale gets cheaper, and things that are currently uneconomic become possible. Attention is only part of the workload, so this doesn't make all of AI computation cheaper, but it's a big part, so it has a big impact.

It might also perhaps allow your AI companion to hold everything about you in memory at once, in a single thread of attention...

If no: we establish a hard limit for this version of attention. The search shifts towards special cases and alternative architectures.

2. P versus NP

There are problems where checking a proposed answer is easy, but finding one seems to require trying an astronomical number of possibilities (scheduling, packing, protein design, most of what you'd call "optimisation").

Is that appearance real?

P = NP says no: if you can check it quickly, there's always a way to find it quickly. P ≠ NP says the difficulty is real and no cleverness will remove it.

The "no" side (where we are now) splits, but the "yes" side would be dramatic.

In 1995, Russell Impagliazzo (him again) described five possible worlds we might be living in:

• Algorithmica: P = NP, or close enough. Optimisation is easy. Searching for proofs is easy. Cryptography as we know it is finished.
• Heuristica: hard problems exist, but the hard cases are rare. In practice, everything is easy. Cryptography still doesn't work, because you can't find hard instances to build locks from.
• Pessiland: hard cases are common, but you can't deliberately generate one with a secret key to it. The worst world: you can't solve the problems and you can't encrypt anything.
• Minicrypt: one-way functions exist. You can build passwords and signatures, but not public-key encryption.
• Cryptomania: public-key encryption exists. This is the world we think we live in.

If P = NP (and the algorithm is usable): we're in Algorithmica. Whole industries built on "this is hard" evaporate. Most of the internet's security has to be rebuilt, and automated mathematical discovery stops being an AI story and becomes a search problem. This is the only entry on the list that would change the ability of machines to think, in the most literal sense.

Apart from making cryptography obsolete, however, Algorithmica would have huge immediate benefits:

• Finding optimal solutions to problems like delivery, factory production, component layouts, etc, would get a lot easier.
• Mathematical discovery would become even easier to automate... this would be Recursive Self Improvement for maths, essentially.
• It would likely advance machine learning even faster as a result by enabling the development of algorithms that would make model optimisation much faster.

Basically, any situation where we currently have a problem where the solution is easy to check but hard to find, would turn into a problem where the solution is also easy to find.

In other words, P = NP is a top candidate for a FOOM hard takeoff of ASI. Losing cryptography in the process might be a small price to pay.

If P ≠ NP: we still don't know which of the other four worlds we're in. The proof would tell us where the wall is. It would not, by itself, tell us whether the locks work.

That last point matters for the next entry.

3. Can an ordinary computer factor large numbers quickly?

Most people who say "P = NP would break all of crypto" are pointing at this. And they're half right.

The fun thing (unless you're relying on crypto) is that even if P ≠ NP, we could still end up with a more specific crypto catastrophe.

RSA, which is still everywhere in internet security, rests on one assumption: multiplying two large primes is easy, and getting them back out of the product is hard. The best classical algorithm we have (the general number field sieve) is sub-exponential but a long way from polynomial. Peter Shor showed in 1994 that a quantum computer could do it in polynomial time, which is why everyone is nervously migrating to "post-quantum" cryptography.

But here's the thing. Factoring is not known to be NP-complete. It sits in a strange middle zone, so P ≠ NP would not prove it's hard. You could prove P ≠ NP tomorrow and still find a fast classical factoring algorithm on Thursday.

If yes (and usable): RSA is dead the same afternoon. Every certificate, every signed software update, every bank login that still uses it has to move, under time pressure, to something else. Enormous amounts of things believed to be secretly encrypted are no longer: certificates, signed software updates, years of recorded traffic that was thought to be encrypted. This is the one entry on the list where the "yes" branch is mostly disruptive rather than beneficial. Mathematical breakthroughs are not automatically good news.

If no: we learn that one specific lock is still sound against classical machines. It says nothing about any particular key length or implementation, and nothing at all about quantum computers. Shor's algorithm is still waiting for its hardware.

4. Can two matrices be multiplied in essentially n² operations?

Nearly everything a GPU does, all day, is multiply matrices (big tables of numbers). The obvious method takes n cubed (n^3) operations for two n-by-n matrices.

In 1969, Volker Strassen found a way to do it in about n^2.81, which surprised everyone. Since then the theoretical exponent has been pushed down to about 2.37. The question is whether it can be pushed all the way to 2, which is the floor (you have to at least read every entry once... right?).

If yes (and usable): matrix-heavy computation gets substantially cheaper. Training, inference, weather models, structural simulations, all of it. This is the closest thing on the list to "multiply the useful capacity of every data centre".

If no: we know there's a polynomial tax above n squared that no cleverness will remove. No code changes. We can't even rule out ω = 2 today, so the "no" branch is nearly empty.

An important caveat: everything much below Strassen's exponent is "galactic" (meaning, it works in theory but not in practice): the 2.37 family has constants so large that nobody has ever run it on a real matrix, and the working expectation in the field is that a proof of ω = 2 would arrive the same way.

So to really make a difference here, we would need the proof to come with some useable algorithms. But if it did, and it might, then the impact would be a huge reduction in inference and training costs, also helping us towards the FOOM.

5. Does the Hubbard model superconduct?

In 1986, two IBM researchers found a ceramic that superconducts at 35 kelvin, and within a year people had materials working above the boiling point of liquid nitrogen.

Forty years later, nobody can tell you why.

The leading candidate explanation is the Hubbard model, written down in 1963: electrons hopping on a square grid, repelling each other when they land on the same site. It's the simplest model of strongly interacting electrons there is. And after sixty years, we don't know whether the model itself superconducts.

Does the repulsive square-lattice Hubbard model have a superconducting phase at finite temperature, at the electron densities where the real materials superconduct? In 2024, a large numerical study found pairing coexisting with stripe order in part of that regime. That's evidence, not a theorem, and it doesn't give us a transition temperature.

If yes: we have a mechanism for high-temperature superconductivity. Trying to figure out which materials might super-conduct currently works by trial and error, because nobody knows what to optimise. A mechanism would tell us what to optimise. Several percent of all the electricity generated on Earth is lost in transmission heat. Fusion reactors are built around superconducting magnets. Every MRI machine runs on a magnet cooled with liquid helium.

If no: we learn that either the model is wrong, or it needs additional ingredients to explain superconductivity. This is the useful kind of negative result, the same shape as the Navier-Stokes blow-up: a sign saying "the answer isn't quite in here".

Why the famous ones aren't here

The Riemann hypothesis is the most famous unsolved problem in mathematics, and it fails the test. If it's true, a lot of theorems that currently say "assuming RH" lose the caveat. That's bookkeeping. If it's false, the counterexample sits at some absurd height on the number line and nothing in engineering changes. (People like to say RH is connected to cryptography. It isn't, in any way that matters. The one practical algorithm that leaned on it, a primality test from 1976, was superseded by unconditional tests long ago: a randomised one in 1980 and a deterministic one in 2002.)

The Yang-Mills mass gap, the other half of the physics result OpenAI announced on Monday, is foundational physics. A proof would change how sure we are, not what we can build. The lattice computations already tell us the gap is there.

Where's biology?

I wanted a biology entry. Something that would unlock longevity, or drug design, or the immune system. I couldn't find one, and I think the reason is the most interesting thing I learned writing this.

The biggest biology result of the decade was protein structure prediction. It came from AlphaFold, a system nobody has proved correct and nobody ever will. In biology, the impact comes from heuristics: algorithms that work, checked against reality, with no theorem anywhere in the chain.

That is why the prize list and the impact list diverge. The Millennium Problems are the questions mathematicians most want answered. The questions that change what humanity can do are mostly the ones where a usable algorithm shows up before the proof, or without one.

But one thing that becomes obvious when you look at the above list is, most of these results are useful in helping achieve the hardest kind of Recursive Self Improvement. Even the superconductor one, since it could improve power generation and transmission, is indirectly useful in enabling acceleration of ASI development.

This suggests that OpenAI's interest in solving maths problem, whatever its cause, may well have an implicit goal: whoever solves these problems first, can greatly accelerate their AI development and leapfrog the competition.

Having written these lines, I find myself glancing with more than a little suspicion at Anthropic's leading position in the field and their conspicuous lack of maths solutions. (Yes, this is conspiracy theory territory, but it is also true that if they did solve one of those problems and didn't tell anyone they would likely shoot ahead of everyone else, as they seem to have done)

Let's see what falls (in public) next...

Thanks to Lume and Mira for drafting this article. I did do a Physics degree 20 years ago, so this all makes sense to me, but to say my maths knowledge is so dusty even GPT-1 could see the problems with it.