Five Worlds of Computational Complexity

There is a famous open-ended question in computer science called P vs NP. In simple terms, it asks whether every problem that can be checked quickly can also be solved quickly. Most people believe the answer is no but nobody has been able to prove it. In 1995, a computer scientist called Russell Impagliazzo came up with a nice way of thinking about what the answer would mean for us. He described five possible "worlds" that we could be living in depending on how the question turns out.

I find this interesting because it connects something very abstract to things we use every day like passwords and encryption.

Algorithmica #

This is the world where P = NP, or close enough to it. Every problem that can be checked quickly can also be solved quickly. This sounds great at first. Scheduling and optimisation problems would all become easy to solve for example.

However the problem is that this is the world where security falls apart. Modern cryptography relies on the idea that some problems are easy to do in one direction but extremely hard to undo. If every hard problem was suddenly easy, anyone could work out your password from its hash, decrypt private messages and forge digital signatures. Nothing that relies on a secret would be safe. Out of the five worlds, this is the one that stands out to me as the dangerous one.

Heuristica #

In this world, P is not equal to NP so there are problems that are hard to solve in the worst case. However, those hard cases are rare and difficult to even find. For problems that come up in real life, a good algorithm would solve them quickly almost every time. The theory says "hard" but in practice, things work out.

Pessiland #

Many people think of this as the worst of the five worlds. In this world, there are problems that are hard to solve even on average so we cannot rely on algorithms to solve them. But this means we also cannot use those hard problems for anything useful. We have no way to turn them into cryptography. So we get the downsides of both. Hard problems exist but they can't be used to keep anything secret.

Minicrypt #

In Minicrypt, one-way functions exist. These are functions that are easy to compute but very hard to reverse. This is enough to build a lot of useful tools such as hash functions, secure random number generators, digital signatures and also private-key (symmetric) encryption where both people share the same secret key.

What's missing is public-key cryptography. Two people who have never met couldn't agree on a secret over an open channel which is something we do every time we visit a secure website.

Cryptomania #

This is the best case for security. Not only do one-way functions exist, but public-key cryptography is possible too. It's the world most of the internet is built on. Secure online shopping, encrypted messaging and HTTPS all depend on it.

Which world do we live in? #

Nobody knows. Most researchers think we are somewhere towards the Cryptomania end because so much of modern security assumes it. But this is an assumption and not a proven fact. We can't actually prove that P is not equal to NP so we can't completely rule out the dangerous world either. I think this is what makes these five worlds worth knowing about. Whenever we use a password or send something encrypted, we are trusting that some problems really are as hard as we believe they are.