P vs NP: A quick introduction

You may have heard a lot of buzz about this whole P vs. NP thing that people tend to get all worked up about. Some people even say it’s the most important open problem in computer science. So what the heck is it?

P and NP are both sets of problems. Specifically, they are sets of decision problems, or problems for which the answer is always “yes” or “no”. Examples of decision problems are things like “is this number prime?” or “can you put these objects on this see-saw so that it is balanced?”. An example of something that’s not a decision problem is “how many primes are less than 1,000”, because the answer is a number, not “yes” or “no”.

So P and NP are sets of decision problems. Alright, so what’s P? P, informally, is the set of decision problems that can be solved “quickly”. When cs people talk about something happening “quickly”, they generally mean it happens in polynomial time (that’s where the “P” comes from). What does that mean? Well, computer scientists like to rate the performance of a program based on how much longer the program takes to run when the input to the program gets bigger.

Time Complexity

Say we’re given a list of numbers, and we’re asked to determine if any of the numbers is even. That’s a pretty easy problem to solve with a program: we just go through the list of numbers and check if any one of them is even (probably by moding the number by 2 and checking if it’s zero, or maybe just be checking that the least-significant bit is zero). If any of the numbers turn out to be zero, then we answer “yes”, and if not, we answer “no”.

So how long does this program take to run in the worst case? Well, in the worst case, we’ll have to check every single number, see that none of them are even, and come back with the answer “no”. So if we had 100 numbers to check, we’d have to check all 100 of them. How long would this take? Well, I don’t know. It depends on a lot of stuff, like the computer you’re running the program on, and how exactly you’re checking if a number is even. An easier question to answer is “if you doubled the input size from 100 to 200, how would the program’s running time change?”. The answer to that is easy, it will also double. And if we quadruple the input size, the running time will also quadruple. We describe algorithms like this one by saying they run in linear time. We say this because the function correlating the input size to the running time is some linear function, like $f(n) = 14n$, where n is the size of your input. Or maybe it’s $f(n) = 100n$. I don’t know. Like I said, that would depend on exactly how you’re running the program. Instead of worrying about the constant, we just say that the program runs in $O(n)$ time. (for our purposes, $O(n)$ is just some special notation used to represent some arbitrary linear function – see wikipedia for a more complete explanation)

We might be able to imagine other algorithms that run more slowly. What about a program that looks at a list of numbers and checks if any two of them are co-prime (ie, if any two of them have no common factors). Such a program might decide to go through all possible pairs of numbers. If you only had, say, 4 numbers, then there are only 16 pairs to check (well, a bit less than that, really, since we want to ignore duplicates). If you double the number of numbers you have to 8, though, the number of pairs goes up to 64. We’d describe this algorithm as running in quadratic time, or that it runs in $O(n^2)$ time. [1]

Okay, so we’ve got problems, and these problems take a certain amount of time to run. We’re interested in the problems that take polynomial-time to run. This means that their running times look something like $O(n)$, or $O(n^2)$, or $O(n^6)$, or really $O(n^p)$, where $p$ is any number. All expressions of this form are polynomials, and all programs that run in $O(n^p)$, for some $p$, are said to run in polynomial time.

Verifying problems

Ok, so that’s what polynomial time is. And like we said, P is the set of decision problems that can be solved in polynomial time (ie, solved “quickly”). So what’s NP? NP has a technical definition that you can look up if you’d like (it has to do with non-deterministic turing machines [2]), but for our purposes, we’ll describe NP as the set of decision problems that you can verify in polynomial time.

What does it mean to verify a problem? Well, consider this (classic) problem: I have some set of numbers. I want to see if I can pick out some of those numbers such that if I add all the numbers together, I’ll get 0 (and I’m not allowed to just pick nothing – I have to use at least one number). This problem might be kind of hard to solve. It seems like you’d sort of just have to try out different combinations of numbers and see if they add up to zero. But verifying a solution to this problem is easy. In other words, if I gave you a set of numbers and asked you to see if it was a solution, you’d have absolutely no trouble doing that. All you need to do is add up the numbers I gave you and see if they added up to 0 or not. That’s really easy to do in polynomial time. So, because I can verify a solution to this problem in polynomial time, this problem belongs to NP.

If I didn’t give you a solution, though, this probably seems like it might be pretty hard. In fact, it seems like one of the only things you could do to solve this problem is to try all $2^n$ different combinations of numbers you could take from your set (where n is the size of the original set). Is there actually a better way of solving this problem? Is there a way of solving it in polynomial time (because $2^n$ is not a polynomial)? Interestingly enough, nobody really knows.

P = NP ?

So this is the real question we’re concerned with. Is the set of problems in P actually the same as the set of problems in NP? We’re basically asking this: “if a problem’s solution can be verified in polynomial time (ie, quickly), does that mean we can also generate a solution to the problem in polynomial time (quickly)?” If P turns out to be equal to NP, it would imply that any problem whose solutions can be verified quickly (and there a lot of problems like this) can also be solved quickly, which is a pretty big deal. There are some “tools” people have developed to help (potentially) make this problem easier to solve.

NP-complete

Taking a step back from the whole P = NP thing, let’s ask a different question: out of all the NP problems, which ones are the hardest? Well, we don’t really have a definition for “hardness”, but we’ll use some intuition. Let’s pretend were talking about mountain climbing. I’m not a mountain climber, but I’d imagine Mount Everest is pretty hard to climb. In fact, I would probably say something like “if you can climb Mount Everest, then you can climb any other mountain too”. This statement makes sense. If you have the skills necessary to climb Mount Everest, you also have the skills to climb any other mountain. On the other hand, if you come and tell me that you can climb this hill in your back yard, that doesn’t say much about your ability to climb a real mountain, precisely because climbing a hill in your back yard isn’t hard.

So let’s extend this thinking to problems in NP. We might say that a problem is considered “hard” if being able to solve that problem will also let you solve any other NP problem you want in polynomial time. Such problems are called NP-hard. In other words, say that I had some random NP-hard problem, and I also had a magic box that could just automatically tell me the answers to that NP-hard problem (the box would have to “run” in polynomial time). Then, using this magic box, I can solve any other NP problem I want.

Note that the definition of NP-hard doesn’t explicitly say that an NP-hard problem has to be NP itself. It’s perfectly possible to have a problem whose solutions are not verifiable in polynomial time, but is still NP-hard (ie, a magic box for that problem will let us solve any NP problem). If an NP-hard problem also happens to be in NP itself, then we call that problem NP-complete.

Being NP-complete sounds like a bit of unique property. Just because I can solve this one particular NP problem, it doesn’t seem like I should magically be able to use that solution to solve all other NP problems. But it turns out that there are actually quite a lot of problems that are NP-complete. For example, the problem I mentioned above where you take a set of numbers and check if some subset of it adds up to zero? (this is commonly referred to as the subset sum problem) That problem is NP-complete (although proving that is a bit involved). This means that if you figured out a way to solve the subset sum problem in polynomial time, then you’ve also figured out how to solve any NP problem in polynomial time. And if you can solve any NP problem in polynomial time? Well, then, P = NP.

So interestingly, no one has yet been able to figure out a way to prove that the subset sum problem or any other NP-complete problem can be solved in polynomial time. This makes a lot of people think that it’s actually the case that P != NP. Proving that seems like it shouldn’t be that hard, either. All you have to do is take any NP problem, and prove that no matter what, there’s no way to solve that particular problem in polynomial time. But no one’s been able to solve that either.

And so, P = NP remains an open problem. If you feel up to, learn more about it (in particular, learn more about turing machines, which are how computer scientists formally talk about problems and algorithms). Maybe you can prove it one way or another (and win millions of dollars!)


[1] After thinking about it a bit I'm not 100% sure that this problem is $O(n^2)$. The point of the example was to illustate a problem where you had to check all posible pairs of the inputs you're given, which is the case in this problem, but I had also intended to have the checking of each pair take constant time, which is not the case in this problem (ie, you can't "instantly" know whether or not two numbers are co-prime). However, given a reasonable constraint on the input (ie, all numbers are between 1 and 1,000), this problem should in fact be $O(n^2)$.

[2] Non-deterministic turing machines can sort of be regarded as "hyper-parallel" computers. Ie, they're computers that can spawn as many threads of computation as they want. NP is actually defined as the set of problems that can be solved in polynomial time by a non-deterministic turing machine. This definition ends up being equivalent to problems whose solutions are verifiable in polynomial time. The reason is that a non-deterministic turing machine can just spawn different threads that generate every possible solution and check them all at the same time. If each individual verification thread runs in polynomial time, and they're all being run at the same time, then the entire non-deterministic machine runs in polynomial time.