What is P ?= NP and why should you care?

After my last blog post, readers remarked that they had no idea what
"P ?= NP" was and that I had completely failed to explain what I was talking about. They are correct. This entry is to remedy that problem.

First an analogy: Suppose you have a jigsaw puzzle. Assembling the puzzle correctly is difficult. But, if someone has the puzzle completed, one can generally tell at a glance that the puzzle is correct. (This isn't strictly true if you are dealing with someone like me who as a little kid would sometimes shove the pieces to fit in where they didn't belong. If one does this to sections that depict sky and clouds, it can be quite hard to tell that it is wrong.) But it seems that it is very difficult to tell how to assemble a puzzle. Moreover, it isn't even clear if one has all the pieces of the puzzle until one is nearly done with the puzzle. It can be a very frustrating experience to be nearly done with a puzzle and then realize that pieces are missing. What if there were a way to tell just from looking at the jumbled pieces in the box if one had the all pieces? Whether P is equal to NP is essentially asking if this is possible. The general consensus among computer scientists is that P is not equal to NP which means that puzzle-solvers are out of luck.

Let's break this down further. P is the set of types of puzzles that can be essentially solved quickly. So for example, "Is a given integer even or odd?" is a problem that lies in P. Given an integer, one can just look at the leading digit and see if it is even or odd. (I'm assuming that our integers are written in base 10). Similarly, the problem "given integers a and b, does a divide b?" is in P,;all one needs to do is divide a into b and see if there is a remainder. But not everything is necessarily in P. For example, the question, "is a given integer composite?" is not obviously in P, since checking requires successive search for divisors.

But, there is a larger class of problems, NP, which are problems which, if they have an answer of "yes," one can quickly convince someone else of the answer if one has the right information. In this context, "is an integer composite?" is in NP, since if I know a non-trivial divisor of the integer, and I want to convince you that it is composite. I can just tell you that number and you can check yourself. To make this more concrete, if I gave you the number 1517 and asked you if it were prime or composite, you would have to do a lot of unpleasant arithmetic. But, if told you 1517 is 37 times 41, you'd be able to check this easily.

Now, it actually turns out that whether a number is prime composite can actually be checked quickly using something called the AKS algorithm . This result was a very big deal, proven by Manindra Agrawal and two other mathematicians in 2002 . I remember when this happened. When the result was announced, I was a high school student who was then at PROMYS, a summer math program at Boston University, and people were distributing and looking over copies of the preprint. The algorithm they used was straightforward, but proving that algorithm really did what was claimed required deeper mathematical results from the area known as sieve theory.

Let's try to make these notions of P and NP more mathematically rigorous. To do that, we need a rigorous notion of what it means to calculate quickly. We want the length of time it takes to run our algorithims to solve our problems to not grow very fast. When mathematicians want something that doesn't grow too quickly, they often look at polynomials (that is, functions like n^2, or n^3, or n^4 +10n +2, as opposed to say exponentials that look like 2^n or 3^n). So, we will define an algorithm to be quick if the amount of time it takes to run is bounded by a polynomial of the length of whatever we inputted. So ,for example, in our earlier case of looking at whether an integer is prime or composite, the length of the input would be the number of digits in the integer. Thus, Agrawal constructed an algorithm that ran would when given an integer always tell you if the integer was prime or composite. Agrawal showed that there is a constant K such that his algorithm terminates in at most at most Kn^12 steps, where n is the number of digits of of the number to be test.

Whether P = NP is one of the great unsolved problems of modern mathematics. P ?= NP is one the seven Clay Millenium Problems, each of which has a million dollar prize. Moreover, there are many practical applications. There are many practical problems which appear in some form to be in NP, but have no known quick algorithm to solve them. These include problems in protein folding, circuit design, and others areas.

Readers have likely also benefited more directly from practical issues related to this problem without even realizing it. I've discussed on this blog before the Diffie-Hellman algorithm. This is one example of many cryptographic systems that are used by modern computer networks, most often without users even realizing that they are being used. These all rest on certain problems being easy to solve if one has extra information, but very difficult otherwise. Thus, if P = NP, then all these algorithms will become insecure. This would be bad. Unfortunately, the converse does not follow: There is a common misconception that if P is not equal to NP, then modern encryption is actually safe. This doesn't follow. It turns out that claims that encryption works implies that P is not equal to NP, but the reverse doesn't follow. It is conceivable (although unlikely) that P and NP are distinct and encryption still collapses. But, figuring out whether P = NP would be a major step in understanding whether or not encryption is really safe.
Those worried about the encryption for their bank accounts can rest easy. Most experts in the field seem to think that P and NP are distinct. This means your encryption is secure. On the other hand, this also means that a lot of practical problems are genuinely tough. One can't have it both ways. Either one gets lots of helpful fast algorithms or one gets good encryption. Right now, it looks like one gets good encryption.

So, how close are we to actually answering if P = NP? This looks pretty far off right now. There are a few methods that look somewhat promising, but a lot of the best current results are results that essentially show that certain techniques cannot answer the question. So right now resolving the question looks pretty far off.