You know when you wake up from a dream and you can’t tell if it has happened in real life or not? This is what happened to me after waking up from the weirdest dream the other day. I’ll spare you the details, but I woke up convinced that P=NP. Many of you may not even know what the hell I am talking about, but some may have immediately understood why I thought I was going crazy. Hopefully, after this post you’ll understand my restless awakening. Enter complexity theory.
So what exactly is complexity theory? In computer science we don’t just care if a problem can be solved, we also want to know the cost of getting to that solution. This is increasingly important as the problem scales and we need to solve bigger and more complex problems.
Complexity theory classifies problems based on the resources they consume to be solved: we are mainly interested in the computational steps to a solution (time) and the memory required to solve it (space). There are other complexity metrics we could choose, but these are the canonical ones. Leveraging this, complexity theory helps us categorise problems into “hard” and “easy”, and allows us to compare problems, algorithms, and solutions 1:1.
But we can see complexity theory from a more philosophical and physical perspective. This is the one shared by one of my favorite theoretical computer scientists, Scott Aaronson (yes, I have a favorite theoretical computer scientist, I am that kind of nerd :) ). His book Quantum Computing Since Democritus is what introduced me to this philosophical perspective of complexity theory. The story of how I ended up reading this book, and how it became one of my bedside books is quite fun, but I’ll leave it for some other post.
Anyway, we can think of complexity theory as the physics of information. Just as thermodynamics tells us we can’t create energy from nothing, complexity theory tells us there are hard limits on what we can compute in a reasonable amount of time. It separates the problems that are merely tedious from those that are fundamentally intractable. It helps us distinguish between computability (can this be solved at all?), and complexity (can this be solved before the universe ends?) of a problem.
Practically, what we use to analyse the complexity of an algorithm and be able to compare them in computer science is the Big-O notation. The Big-O notation measures the rate of growth of a specific metric, and is what we use to categorise algorithms into different complexity categories. Is often used to express bounds on the growth of an arithmetical function. To understand this, imagine you are in a library containing n books, the complexity of an action depends on what you are doing.
O(1) - Constant: You grab the very first book off the shelf to read. It takes the exact same amount of time whether the library has 10 books or 10 million. This is trivial.
O(log n) - Binary Search: You are looking for a specific title on a shelf where the n books are perfectly alphabetized. You look at the middle book, see if your title comes before or after, and ignore the other half. By repeatedly cutting the problem in half, you can find your book among millions in just a few steps. This is incredibly efficient.
O(n) - Linear Search: You are looking for a specific title, but the n books are completely scattered on the floor. You have to pick up every single book one by one until you find it. If you double the number of books, you double the time.
O(n²) - Quadratic: You want to check if the library has any duplicate copies of the n books, but you have no catalog. You pick up the first book and compare it to every other book. Then you pick up the second and compare it to the rest. If you double the number of books, the work quadruples.
O(2ⁿ) - Exponential: You want to find a specific combination of books that fits perfectly into a small display case. You have to test every possible subset of the n books to see if they fit. Adding just one book to the library doubles the number of possible combinations you might need to check. This is where computers choke.
We are getting closer to understanding where that P in P=NP comes from: polynomial time (P) includes the searches that are feasible (Linear, Binary, or even Quadratic). Exponential time is the password search—problems that become impossible to solve as soon as the input gets slightly large.
We are now ready to explain what P and NP means. P (Polynomial Time) refers to the set of problems that computers can solve quickly.
Think of Matrix Multiplication in Deep Learning (using a trendy algorithm for the time we live in). When you run a forward pass on a model like GPT, you are performing billions of operations. However, the cost grows polynomially with the size of the matrices. It is computationally heavy, but deterministic and “efficient” in the eyes of complexity theory.
NP (Nondeterministic Polynomial Time), on the other hand, refers to problems where if I gave you a solution, you could verify it quickly, even if finding that solution is impossibly hard.
Let’s use the classical examples of integer factorisation (one of the hard problems that is the basis of modern cryptography along with the discrete logarithmic problem). If I give you two large prime numbers, multiplying them to get a public key is trivial (P). But if I give you the public key and ask for the original primes, you are stuck, this is computationally intractable for classical computers (leave quantum computing aside for now). However, if a hacker guessed the primes, verifying they are correct is as simple as running a single multiplication on a calculator. This asymmetry, hard to find, easy to verify, is the hallmark of NP.
This leads to the million-dollar question, Is P = NP? I.e if checking the answer is easy, is finding the answer also easy but we don’t know yet how to do it? Is there a secret trick that turns integer factorisation into something tractable as matrix multiplication?
Within the realm of NP, there is a distinct class of problems known as NP-Complete. These are not just “hard” problems; they are the “universal” hard problems, defined by the property of reducibility.
A problem is NP-Complete if any other problem in NP can be translated (or “reduced”) into it in polynomial time. The canonical example is Boolean Satisfiability (SAT), the problem of determining if there exists an interpretation of variables that satisfies a given Boolean formula. The Cook-Levin theorem proved that checking a Sudoku solution, verifying a Traveling Salesman route, or validating a protein structure can all be mathematically rephrased as a generic SAT logic puzzle.
This means that NP-Complete problems act like a skeleton key. If you find a polynomial-time algorithm for just one of them (like 3-SAT or the Traveling Salesman Problem), you have implicitly found a fast algorithm for every problem in NP. You solve one, you solve them all.
But there is a level beyond even this: NP-Hard. While NP-Complete problems must be inside NP (meaning checkable in polynomial time), NP-Hard problems have no such restriction. They are at least as hard as the hardest problems in NP, but they don’t necessarily play by the rules of “easy verification.”
The Distinction: All NP-Complete problems are NP-Hard, but not all NP-Hard problems are NP-Complete.
The Implication: An NP-Hard problem might be so difficult that you can’t even verify the answer quickly—or in some cases (like the Halting Problem), you can’t solve it at all.
This got a bit convoluted, so let’s come back to our matter at hand. Why I was so anxious about the possibility of P=NP?
If P = NP were proven true, the consequences would extend far beyond efficient delivery routes. It would represent a total collapse of the cryptographic hierarchy we rely on.
As glimpsed above, modern cryptography (like RSA and Elliptic Curve cryptography) relies on the existence of one-way functions based on hard mathematical problems, i.e operations that are easy to compute but computationally infeasible to invert (e.g., f(x) is easy, f^{-1}(y) is hard).
If P = NP, then one-way functions do not exist. Deriving a private key from a public key would become a polynomial-time task, rendering virtually all digital security obsolete overnight.
Conversely, in the field of AI and Optimization, P = NP would be the Holy Grail. Training neural networks currently relies on stochastic gradient descent to approximate a local minimum of a loss function—a heuristic process. If P = NP, we could theoretically solve for the global optimum of the loss function directly and deterministically. We wouldn’t just be “learning” patterns. We would be calculating the perfect solution to optimization problems instantly.
I guess by now you have a better understanding of why I thought I was crazy when I woke up thinking P=NP. If it was just me that knew, that’s cool, it would be like having a super power.
Unfortunately, it wouldn’t be long until someone else realised, and our whole reality and digital existence would collapse, shaking the foundations of our system. I keep making this point, but understanding math and physics is the only way of understanding our reality (or the simulation).
Final note: After writing this post and before scheduling it, I coincidentally came across the following article from quantum magazine discussing complexity theory and the role of oracles in theoretical computer science (fun story: I still remember those “random oracles” that we used to proof cryptographic primitives in college :) Happy to write a post about the role of oracles if this is of my audience’s interest).