What happens in practice if the P=NP problem is solved?
With the recent astonishing progress of AI at solving major maths problems like Navier–Stokes (or stealing a partial proof and finishing it, but that’s a story for another time) and formalising Fermat’s Last Theorem, the possibility an AI decides if P=NP has suddenly become a real possibility. So if it did, what would happen?
I’m not going to worry about how this would affect computing researchers. They would all get very excited, and some of them might get angry, but worrying about this is kind of their job. So, what about everyone else?
Firstly, extremely briefly, what is the P=NP problem?
One issue with this is that it’s easy to give an explanation that is subtly wrong, because I have to use words like “fast” which have a specific theoretical meaning (polynomial time) which doesn’t line up with people’s expectations – in fact we are going to see that later in this post.
So let’s give a simple, and wrong, description:
If P=NP, then if you can quickly check if a guess of the answer to a problem is right, you can quickly find an answer without a guess, or prove there is no answer.
For example, consider a Sudoku puzzle. It’s easy to check the answer: check if every row, column and box contains 1–9. This means if P=NP, then we can solve Sudoku fast.
On the other hand, if you handed me a filled-in cryptic crossword, I still couldn’t necessarily be sure you’d done it right – so not all problems are easy to check.
You sometimes hear horror stories about P=NP: encryption would be broken, banking would collapse, and so on. And there is a world where that happens, but it’s far from the only possibility.
It’s proved that P != NP
This is (in my opinion) the most likely option.
In this case nothing changes.
The world is already set up for this – we would just know that there isn’t a polynomial-time algorithm for SAT, or any other NP-complete problem. Of course people would still work on theoretically and practically solving particular problems faster, the same way we have for decades.
P=NP, non-constructively
This would mean we know you can solve NP problems in polynomial time, but we don’t know how.
This would be a very weird and annoying world to live in (for me at least), but nothing changes in practice. Of course everyone immediately tries to turn the proof into a real algorithm, which slides us into one of the next few worlds.
P=NP, with an \(O(n^{100})\) algorithm
So we can solve NP problems in polynomial time, the exponent is just absurd. To be concrete, let’s imagine \(n\) is the size of the input to a SAT solver.
In this world, again, nothing changes.
Even solving \(n=2\) with our new algorithm requires \(2^{100} \approx 10^{30}\) steps.
That is already hopeless, and interesting SAT problems have inputs vastly larger than 2. So we have a cute result but nothing useful.
Clearly 100 is deliberately silly, though.
What about 30?
Still silly.
20?
Still silly.
10?
Surely by now we have to start caring?
P=NP with an \(O(n^{10})\) algorithm, or lower
Let’s consider when we actually need to start worrying. \(n^{10}\) looks scary. But is it?
Even a problem of size 20 – still uselessly small – needs \(20^{10} \approx 10^{13}\) steps.
Let’s start being specific. First, let’s separate out the time and space requirements, then let’s pick a real problem.
I went looking for the smallest SAT instance I could find which corresponds to breaking a real, full-strength cryptographic primitive rather than a deliberately reduced toy cipher. The smallest clean example I could find is from work on attacking full AES-128 using SAT.
The AES computation there becomes a SAT formula with 9,152 Boolean variables and 188,664 clauses. The researchers do not just hand this formula to a SAT solver and recover the AES key. They make the attack practical by supplying the solver with extra information about intermediate S-box values obtained from a side-channel attack. In other words, even this rather small SAT encoding needs help before it becomes a useful key-recovery attack.
I can’t promise this is literally the smallest interesting cryptographic SAT instance anyone has ever written down. That would be a rather difficult claim to establish. There are also very small SAT benchmarks derived from reduced cryptographic constructions – for example reduced AES-like instances with only hundreds of variables – but those are not attacks on full AES-128.
This is simply the smallest full-strength, genuinely security-relevant example I could find, and it is tiny compared with the million-sized input I originally had in mind.
Now comes another piece of cheating.
The \(n\) in \(O(n^6)\) means the size of the input. So \(n\) is not 9,152, the number of Boolean variables.
It isn’t really 188,664 either. There are 188,664 clauses, and every clause has to contain variable identifiers, signs, separators and so on. The actual encoded input length is therefore considerably larger. But I want to be as unfair as possible to my own argument, so I am going to pretend:
\[ n=188,664. \]
One unit per clause. This is definitely an underestimate of the actual input size. Now:
| Algorithm | Work for \(n=188,664\) |
|---|---|
| \(n^{10}\) | about \(6\times 10^{52}\) |
| \(n^6\) | \(4.5\times 10^{31}\) |
| \(n^5\) | \(2.4\times 10^{26}\) |
| \(n^4\) | \(1.3\times 10^{21}\) |
| \(n^3\) | \(6.7\times 10^{15}\) |
So let’s make some crazy assumptions. You are a government. You have huge amounts of highly parallel computing power. Let’s assume the algorithm parallelises perfectly, which isn’t guaranteed at all. Let’s also pretend one step of our SAT algorithm corresponds to one operation on the machine.
A present-day top supercomputer can do around \(2\times 10^{18}\) floating-point operations per second. This comparison is already ludicrously generous. A floating-point benchmark operation is not remotely the same thing as an arbitrary step of a SAT algorithm. But fine. Let’s give the attacker that.
At \(n^6\), we need roughly \(4.5\times 10^{31}\) operations.
At \(2\times 10^{18}\) operations per second, that is around 700,000 years for one key.
Fine, says the government. We’ll buy a thousand of these supercomputers. Now it takes centuries. A million of them? We are getting towards a year, assuming a million of the world’s fastest supercomputers can cooperate with literally perfect efficiency on one SAT problem.
I think at that point we can safely call the algorithm useless, and remember, I deliberately made \(n\) too small.
What about \(n^5\)? That is about \(2.4\times 10^{26}\) operations. Under our fantasy assumptions, that is a few years on one of the fastest machines in the world.
Now we are entering a slightly different world. A government probably isn’t going to run that to read my email. But perhaps a government with lots of hardware and a sufficiently important key starts thinking about it.
At \(n^4\), we have about \(1.3\times 10^{21}\) operations. Under these ridiculously favourable assumptions, that’s minutes.
Now we panic.
So as you can see, the exponent at which we have practical concerns is much lower than you might expect. And that was just time.
Space is possibly worse
Suppose our clever new algorithm needs \(n^4\) space as well. For our real, deliberately undercounted AES example, \(188664^4 \approx 1.3\times10^{21}.\)
If one unit is one byte, that is about 1.3 zettabytes of working memory. Not storage. Not every hard disk in a giant archive. Memory that this one computation needs to access while it runs. That’s not happening. Even \(n^3\) space gives \(6.7\times10^{15}\text{ bytes}\), or roughly 7 petabytes of working memory.
So perhaps our P=NP theorem says something like:
\[ \text{SAT takes }\Theta(n^6)\text{ time and }\Theta(n^4)\text{ space}. \]
That is polynomial time. P=NP. And absolutely nobody is using this thing to recover AES keys.
Could there be a hidden \(O(n^2)\) or \(O(n^3)\) algorithm for SAT? Maybe. But this seems much less likely than just P=NP.
A million monkeys have hammered at this problem for years. Finding that SAT is in P would already be astonishing. Finding that, after all this time, it has something like a simple cubic algorithm hiding under the sofa would be several orders of magnitude more shocking again.
Wait, but aren’t SAT solvers exponential? How do they work?
This is the huge difference between worst-case complexity and practical runtime. SAT solvers have exponential worst-case behaviour. This means there are relatively small problems for which they can take an absurd amount of time.
But decades of clever tricks mean they can also solve enormous problems, because they make use of structure, simplifications, learned clauses, propagation, good branching choices and lots of other tricks.
They don’t take \(2^n\) steps every time you give them \(n\) variables. In fact this gives us a slightly strange comparison. Imagine tomorrow someone gives us a shiny new SAT algorithm which is provably \(O(n^6)\). Its worst-case complexity is incomparably better than the SAT solvers we use today. But on our AES instance, \(n^6\) is around \(4.5\times10^{31}\).
If our current supposedly “exponential” SAT solver solves some comparable large instance in a minute, it has obviously done vastly less work than \(n^6\) on that instance. Indeed, it has to be doing vastly less than \(n^3\). So we could prove P=NP, get our wonderful polynomial SAT algorithm, and then carry on using the exponential SAT solver because it’s faster.
A similar case – graph isomorphism
Something a little like this has already happened in graph isomorphism.
There is a tool called nauty which many people use and which is very, very fast. There are other tools too – bliss, for example, and Traces, which is now distributed together with nauty. These algorithms have unpleasant worst cases, but in practice they are incredibly fast on many huge graphs. Then along came László Babai with an amazing result: actually, graph isomorphism can be solved in quasipolynomial time,
\[ \exp((\log n)^{O(1)}). \]
This was a stunning, exciting and clever theoretical result, improving the previous general worst-case bound of roughly
\[ \exp(O(\sqrt{n\log n})). \]
So: lower complexity. Amazing! Speed improvements for everyone! Except no. If I actually have two graphs and want to know whether they are isomorphic, I’m still much more likely to use nauty or Traces.
For any graph where Babai’s algorithm runs in a reasonable amount of time, nauty may well already solve it trivially. The crossover point is hard to measure but potentially massive, and for many of the graphs that come up in practice it may never win at all.
It’s certainly the case that there is no widely used high-speed implementation of Babai’s algorithm.
I tried implementing it myself and quickly realised two things: this was going to be extremely hard, and it wasn’t at all clear that the result would be useful. None of this is a criticism of Babai’s result. It’s an astonishing theorem. It’s just a good example of something that is easy to forget:
A dramatically better theoretical complexity bound does not necessarily give you a faster program.
And the same could happen if P=NP. So if someone announces tomorrow that they’ve proved P=NP, before you change all your passwords, there is one fairly important follow-up question:
What’s the exponent?
AI declaration: I used Codex to help with a literature review for small SAT problems, check all my maths, and do a careful proofread for my horrible spelling and autocorrect typos (I wrote this on my phone). Codex wanted to clean up my rambling and give this a proper three-act structure, but I said no.