Tuesday, June 28, 2011

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.


MKR said...

I just wanted to let you know that I read this. There are still many points that I don't understand, but I will leave discussion to those with the requisite mathematical competence.

Joshua said...

I'm actually sincerely interested in what parts are that you don't understand. If that is the case then I've probably explained something poorly.

MKR said...

Well, for one thing, I don't understand what the memberships of 'P' and 'NP' are supposed to range over. You say, "P is the set of types of puzzles that can be essentially solved quickly." Puzzles of all kind, including, say, your jigsaw puzzle, or just mathematical (or mathematically representable) puzzles? Or perhaps puzzles about numbers? I can't gather any answers to such questions.

"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." "Length" meaning the number of symbols in a mathematical formula? Or the number of digits in a numeral in base 10?

All of these things are unclear to me. I looked at the Wikipedia article "P versus NP problem" and found no answers there.

Joshua said...

Yes, essentially puzzles about numbers. But, there are two important qualifications there: First, essentially all puzzles can be made into puzzles about numbers. Second, in order for this to make sense we need to talk about collections of puzzles. So that's why we look at say "is an integer prime?" rather than "is 1001 prime?". Otherwise the math doesn't work out. Similarly, one would look not at a single jigsaw puzzle but the set of all jigsaw puzzles with some set of constraints.

Your length question is an excellent one. Here's the really cool thing: it doesn't matter. It turns out that almost any natural notion of length you come up with will give you the same results as long as we just care about being bounded by a polynomial and don't care about what polynomial it is. (This is not obvious and takes some work to formulate rigorously and prove but it is essentially true).

Joshua said...

Does that help clarify things?

MKR said...

First, essentially all puzzles can be made into puzzles about numbers.

I am unconvinced. Every drawing by Al Hirschfeld (at least, any made after a certain date) contains the name "Nina" in one or more places, hidden among the lines of the drawing. So each such drawing contains a puzzle, the solution to which is the identification of all the occurrences of "Nina." If you don't like the example, there are certainly drawings made as puzzles in which the object is, e.g., to identify all the faces that are hidden among the lines that make up the drawing. I don't see how such pictorial puzzles can be represented as puzzles about numbers.

Joshua said...

Ok. That's probably a weak point. I should say something like "it seems that almost all puzzles can be essentially made into numbers".

Keep in mind that if a computer can do it, that means that can be thought of in terms of numbers. The face recognition is actually a really good example- humans have a dedicated section of our brains to recognizing faces, and it apparently uses a lot of processing power. But we're getting better. Look at for example cameras that can now recognize approximately where faces our in a picture. In order to do that, engineers needed to come up with mathematical approximations for the notion of what constituted a face.

Similarly, the Nina example is very close to what CAPTCHA systems do to try to tell humans and spambots apart (CAPTCHA systems are the things that ask you to input a word or set of squirrely letters in on some websites to make sure you aren't a bot). You may have noticed that over the last few years the CAPTCHAs have been getting harder and harder to solve. Why? Because the people making the spam bots have been getting better and better at approximating what humans can do, so they need to use a harder CAPTCHA that we can do that the bots still can't do. Eventually, the method will probably fail completely.