The biggest problem in computer science: P versus NP

There are seven maths problems that have been declared so difficult and so interesting that the Clay Mathematics Institute named them the Millennium Prize Problems, and whoever solves one of them receives a prize of one million dollars. One of the problems also touches on computer science, and it is called the P versus NP problem. Let’s explain what this problem is actually about.

Right then. Let’s not kid ourselves that this will be easy to explain. It is a Millennium Prize Problem, after all. So go and make yourself a good cup of green tea 🍵 and let’s get started. First we’ll look at four different problems from the world of computer science and algorithms. We’ll analyse the problems and see how they relate to the letters P and NP.

Problem 1: finding the smallest number

P vs. NP is about algorithms and their complexity. Imagine that I tipped a hundred slips of paper out in front of you, each with one number written on it, and asked you to find the slip with the smallest number. How long will it take you?

Half a minute? Two minutes?

Those are units of time, and in theoretical computer science we aren’t all that interested in them. What interests us more is the number of operations. So we could ask a slightly different question: how many slips do I have to check to be certain that I have found the smallest number? The answer is that I have to check all of them – because the smallest number could be on the very last slip. If I throw a hundred slips in front of you, you must check a hundred slips. If I throw a thousand, you must check a thousand. In general, if I throw n slips in front of you, you must check n slips.

We call this the complexity of an algorithm. If I throw n slips in front of you and you have to carry out n operations to find the smallest number, it means that this algorithm for finding the smallest number has complexity n. We also call this linear complexity, because the complexity is described by a linear function.

All right, you have gone through a hundred slips and announced that the smallest number is 17. How can I check that you are telling the truth? There is no other way than to go through all the slips again and check that none of them has a smaller number. So you have to look at n slips to find the smallest number, and when I want to check it, I have to do the same. The complexity of verifying the result is therefore also n, linear complexity.

Are there algorithms where it is easier to check the result than to find it?

Problem 2: product of a pair

Imagine that I tip out two equally large piles of slips of paper in front of you, again with one number on each slip. Now I would like you to find a number from pile A and a number from pile B whose product is 918. For example, let’s take these piles of numbers:

$\begin{array}{rcl} A & = & {49, 11, 32, 54, 15} \\ B & = & {17, 64, 74, 61, 21} \end{array}$

How can we find a pair of numbers whose product is 918? Well, we can simply try all the possibilities. How many are there? Quite a lot – there are 25. We start by multiplying the first number from pile A, that is 49, by each number from pile B:

$\begin{array}{rcl} 49 \cdot 17 & = & 833 \\ 49 \cdot 64 & = & 3136 \\ 49 \cdot 74 & = & 3626 \\ 49 \cdot 61 & = & 2989 \\ 49 \cdot 21 & = & 1029 \end{array}$

No pair of numbers gives 918. So we try the same with the remaining numbers from pile A: another five pairs for 11, another five for 32, another five for 54 and the last five pairs for 15. In total we can try 25 pairs of numbers. In the end we find that 54 · 17 = 918.

What is the complexity of this algorithm? We are interested in how many pairs of numbers we had to multiply. Both piles contained five slips, and we had to try each of the five numbers from the first pile with each of the five numbers from the second pile. In total we tried 5 · 5 = 25 combinations. If I threw two piles of 10 slips in front of you, you would have to try 10 · 10 = 100 combinations. Generalising, if I throw two piles of n slips in front of you, you must try n · n = n² combinations.

We say that our algorithm has complexity n², quadratic complexity, because it is described by a quadratic function.

But how hard is it to check the result? If you tell me that 54 and 17 are numbers whose product is 918, I no longer have to go through all the pairs of numbers from both piles as you had to. It is enough for me to multiply this one pair 54 · 17 and I will know whether you are right or not. So while solving this problem requires calculating up to n² products, verifying requires calculating only one product. Verification therefore has constant complexity 1.

This makes this task very different from the previous one, where we needed the same number of steps for the calculation itself and for the verification that followed.

This task is also orders of magnitude harder than the previous one. If I tipped ten thousand slips of paper in front of you and wanted you to find the smallest number, you could probably do it in a day. But if I tipped out two piles of ten thousand slips and had you look for the product, you would have to check ten thousand times ten thousand products, which is a hundred million calculations. Even if you tried one product per second, it would take you about three years.

Problem 3: subset sum

Let’s look at the third problem. This time I tip out twelve slips of paper with numbers and I would like you to find any number of slips whose sum is zero. For example:

$A = {24, - 69, 1, - 15, - 76, - 60, 16, - 83, 48, - 22, 54, - 47}$

Choose any group of numbers from these whose sum is 0. For example, the numbers

$24 + 48 - 69 + 1$

add up to 4, so they are not the right answer. The right answer is the group of numbers… and you know what? Try to find it yourself as homework 😉. There is exactly one group of numbers whose sum is 0. At least you will find out how hard this problem is.

Now we need to know the complexity of this problem. Working it out is no longer entirely trivial and it is more for the connoisseurs. So if you are interested in how to work out the complexity of this problem, keep reading. Otherwise you can skip to the next section. ⏩

So how can we find a group of numbers whose sum is 0? Well, we simply have to try all possible combinations of numbers. We have to try all the pairs of numbers, all the triples, quadruples, quintuples and so on, and for each group we have to check whether its sum is zero. How many such combinations are there?

Let’s see it on a smaller set of numbers. How many different groups of numbers, that is subsets, can I make from the three numbers B = {5, 7, 9}? There are eight in total:

$\begin{array}{rcl} B_{1} & = & {} \\ B_{2} & = & {5} \\ B_{3} & = & {7} \\ B_{4} & = & {9} \\ B_{5} & = & {5, 9} \\ B_{6} & = & {5, 7} \\ B_{7} & = & {7, 9} \\ B_{8} & = & {5, 7, 9} \end{array}$

Notice that we have also counted the empty subset B₁. It isn’t very useful right now, but we have left it in for completeness. To simplify the calculation, we assign a binary vector to each subset. A binary vector is simply a sequence of zeros and ones, for instance 00101010. We will work with binary vectors of length three. We assign the vector 101 to the subset that contains “the first and third number from the original set, but not the second number”, that is, to the set {5, 9}. We assign the vector 110 to the subset that contains “the first and second number from the original set, but not the third”, that is, to the set {5, 7}, and so on.

$\begin{array}{rcl} B_{1} = {} & \to & 000 \\ B_{2} = {5} & \to & 100 \\ B_{3} = {7} & \to & 010 \\ B_{4} = {9} & \to & 001 \\ B_{5} = {5, 9} & \to & 101 \\ B_{6} = {5, 7} & \to & 110 \\ B_{7} = {7, 9} & \to & 011 \\ B_{8} = {5, 7, 9} & \to & 111 \end{array}$

We can see that each subset has exactly one binary vector of length three, and each binary vector of length three corresponds to exactly one subset. So if we work out how many different binary vectors of length n there are, we get the number of different combinations we can make when the input is n different numbers. Let’s work it out.

There are two binary vectors of length one: 0 and 1.

We get the binary vectors of length two by taking all the binary vectors of length one and adding 0 to the end of each: we get the vectors 00 and 10. We take all the vectors of length 1 again and add 1 to the end: 01 and 11. That gives us all the vectors of length 2: 00, 01, 10 and 11.

We get the binary vectors of length three by taking all the binary vectors of length two and adding a zero to the end: 000, 010, 100 and 110, and a one: 001, 011, 101 and 111.

And so on for every further length. We can see that when we increase the length of the binary vector by one, the number of different binary vectors doubles. For a vector of length four we would therefore get 2 · 2 · 2 · 2, which is 16, different combinations.

In general, we can deduce that if we have a set M containing n elements, then the number of all subsets of M equals the number of all different binary vectors of length n, and that is equal to

$\underset{n times}{\underset{⏟}{2 \cdot 2 \cdot \dots \cdot 2}} = 2^{n}$

2ⁿ or n² – does it make a difference? 🤷‍♂

So there are 2ⁿ different subsets that we can make from a set of n numbers. In our case we have n = 12 numbers, so we have to check 2¹² different combinations, which is 4096 combinations. We say that this problem has complexity 2ⁿ, exponential complexity, because it is described by an exponential function.

Notice that the previous problem had complexity n², whereas this one has complexity 2ⁿ. They look very similar, don’t they? But there is a big difference between having a constant exponent and having the variable n there. Notice that when n = 4, we get

$\begin{array}{rclrc} n^{2} & = & 4^{2} & = & 16 \\ 2^{n} & = & 2^{4} & = & 16 \end{array}$

Good, so far they come out the same. What if n = 10?

$\begin{array}{rclrc} n^{2} & = & 10^{2} & = & 100 \\ 2^{n} & = & 2^{10} & = & 1024 \end{array}$

Whoa, the exponential function has shot up and is suddenly about ten times bigger than the quadratic one. What do we get for n = 20?

$\begin{array}{rclrc} n^{2} & = & 20^{2} & = & 400 \\ 2^{n} & = & 2^{20} & = & 1 048 576 \end{array}$

For n = 20, the exponential complexity has a value roughly 2,600 times higher than the quadratic complexity. So we can see that an exponential function grows much faster than a quadratic function. Remember that the next time a pandemic comes along and spreads through the population at an exponential rate.

So if I threw twenty slips of paper in front of you, you would have to check 1,048,576 combinations. That is quite a lot.

How do we verify the result?

How long will it take me to verify that the resulting group of numbers really adds up to 0? That will be quite quick: I simply add up this one group of numbers, and if the sum is 0, you have found the right group of slips, and if the sum is different, you have found the wrong set of slips.

Again we see that checking the result is much easier than finding it.

Problem 4: the travelling salesman problem

The travelling salesman problem is one of the most famous algorithmic problems. Roughly speaking, we have a travelling salesman who sells rain. And this salesman has to travel a lot to make a living. So he has decided to visit 14 major cities in Britain. And because he doesn’t want to waste anything, he has decided to find the shortest possible route that takes him through all of those cities. And our job is to find that shortest route.

How can we find this shortest route? We try all the possibilities.

We can simplify things. Let’s imagine that between any two cities there is exactly one shortest route. How can we find the shortest route through all the cities? We have 14 cities, so we have 14 options for where to start. Let’s say we started in Manchester!!! Where can we get to from Manchester? In theory we can go to any of the other cities. So we can choose from the 13 remaining cities.

We can already work out that we have 14 · 13 options for visiting the first two cities – we have 14 options for where to start, and then we choose from the 13 remaining cities.

When we arrive in the second city, we have to carry on. We have already been to two cities, so we can travel to one of the 12 remaining cities. That gives us 14 · 13 · 12 options for visiting the first three cities.

After we have visited the third city, we have to choose one of the 11 remaining cities, then one of the 10 remaining cities, and so on.

When we have visited all of them, we find that we had a choice from

$14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

possibilities. This may remind you of a factorial, which we denote with an exclamation mark. So we can say that this product equals 14!:

$14! = 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

and so there are 14! routes that lead through all 14 cities. Is that a lot? Quite, because

$14! = 87 178 291 200.$

In general, if we were looking for the shortest route between n cities, we would have to try n! different routes. The complexity of this solution is therefore n!.

How would we verify that we have found the right result? If you told me that the shortest route goes from Plymouth to Manchester, then to Leeds and so on, how can I check that you are telling me the truth? Well, that’s pretty hard 🤷‍♂. Because when I look at that route, I have no easy way of checking whether this particular route is the shortest. I actually have to do the whole calculation again. Verifying the result therefore also has complexity n!.

The classes P and NP

We have looked at four problems and the algorithms that solve them, and we have analysed how hard it is to find a solution and how hard it is to check that solution. We can summarise it in this table:

Problem	Complexity of solving	Complexity of verifying
Smallest number	n	n
Product of a pair	n²	1
Subset sum	2ⁿ	n
Travelling salesman	n!	n!

Now we will divide our problems into two groups. The first group consists of problems that are easy to solve. These are problems that can be solved with complexity n or n² or n³ or n⁴ and so on. Because expressions such as n² are called polynomials, we denote this class of problems with the letter P. So we say that the class P contains the problems that can be solved in polynomial time (= they have complexity such as n² or n⁷). Broadly speaking, these are problems that can be solved fairly easily.

The class P therefore includes problem 1, finding the smallest number, because it has solving complexity n, and also problem 2, product of a pair, because its solving complexity is n², and both are polynomials.

The second class is the class NP. It contains the problems that can be verified in polynomial time. The class NP therefore includes all the problems except the last one. We don’t know how to verify the travelling salesman problem in polynomial time. The first three problems can be verified in polynomial time.

We can neither solve nor verify the travelling salesman problem in polynomial time. For the travelling salesman problem we would therefore need yet another class, one containing even harder problems. This class exists, but it isn’t interesting for us at the moment.

It is clear that the class P is a subset of the class NP. That is, every problem in the class P is also in the class NP. This makes sense – if we are able to solve a problem in polynomial time, we are also able to verify the result in polynomial time.

The P vs. NP problem

And does it work the other way round? Is every problem in the class NP also in the class P? That is, if there is a way to verify the result of a problem in polynomial time, is there also an algorithm that would solve that problem in polynomial time?

For example, we know that we can verify the result of problem 3, subset sum, in polynomial time. But to solve it we used an algorithm that is not polynomial; the algorithm we used has exponential complexity 2ⁿ. But do we know for certain that no algorithm with polynomial complexity exists for this problem?

We don’t!

It could well turn out that for every problem that can be verified in polynomial time, there is an algorithm that solves that problem in polynomial time. We don’t know. We can’t prove that such an algorithm exists, but we can’t disprove its existence either.

If for every problem in the class NP there were an algorithm that solves it in polynomial time, it would mean that the class NP was actually equal to the class P. All the problems in P would be in NP and all the problems in NP would be in P – the two classes would be equal, identical.

The P vs. NP problem is therefore the question of whether the class P is identical to the class NP, or whether they are two different classes of problems.

So either P = NP or P ≠ NP. Nobody knows which, and if you work it out, a prize of one million dollars awaits you, along with undying fame and probably also the Turing Award, which is a sort of Nobel Prize for computer scientists.

What would happen if P = NP?

What would happen if P = NP? Well, it isn’t entirely easy to say what would happen. We would know that for every problem in the class NP there is an algorithm that solves it in polynomial time. For example, that for our problem 3, subset sum, there is an algorithm that solves it in polynomial time. But there are three catches:

Knowing that such an algorithm exists doesn’t mean that we are able to find it. We would simply know that yes, there is an algorithm that solves the problem in polynomial time, but we might not be able to construct it for another hundred years. It is a bit like how the general theory of relativity predicted the existence of black holes, yet it still took us several more decades before we managed to take the first “photograph” of a black hole.
Unfortunately, the existence of an algorithm that runs in polynomial time doesn’t mean that it is fast. We could find an algorithm with complexity n¹⁰⁰. After all, even the expression n¹⁰⁰ is a polynomial. If we compare the complexities 2ⁿ and n¹⁰⁰, we find that as long as n is relatively small, the algorithm with complexity 2ⁿ still needs fewer operations. For example, for n = 20 we have 2²⁰ = 1,048,576, whereas the expression 20¹⁰⁰ gives a number with about 130 digits, which is bigger than 1,048,576 by about 120 orders of magnitude. In practice, our polynomial algorithm would therefore be slower than the exponential one – at least as long as n is relatively small.
If we did manage to find a fast algorithm running in polynomial time, we could solve a lot of problems faster and more accurately. That is of course good news, but it has its downsides too. There is a field that relies on some problems being hard to solve, and that is cryptography – encryption. It could happen that it would become much easier to break current ciphers.

Interlude: since you have read this far, as a reward I will tell you that the solution to problem 3 is 24 + 1 − 60 + 16 − 83 + 48 + 54.

What would happen if P ≠ NP?

If it turned out that the classes of problems P and NP are different, then not much would happen, because that is more or less the status quo. At the moment we have no algorithm that solves any hard problem in NP in polynomial time, and if someone proved that P ≠ NP, it would simply stay that way forever. A proof that P = NP would be a far bigger sensation.

References in pop culture

In one episode of The Simpsons we see Homer end up in some kind of alternative reality, in which it is revealed to him that P = NP. You can watch it on youtube.com.
In Futurama, on the other hand, we can see that they have two folders in a warehouse, one labelled P and the other labelled NP. You can watch it on youtube.com.
The second episode of the second series of Elementary, titled “Solve for X”, dealt with the murder of a mathematician who had probably solved the P versus NP problem.

« Previous: What is 1 + 2 + 5 × 0? On the order of operations

Next: Exponential time hypothesis (ETH) »