Why P= NP is important

So, there have been some developments in Wikileaks, but I think I will post those later, just to give some semblance of order to my blog, if not my brain. So we are now on P vs. NP and its relevance.

By, now I hope you are familiar with the P vs. NP problem, but for those of you who are not, see my previous posts here, here and here. Now that everybody should be up to speed, we proceed with the discussion. As you may or may not know, my area of speciality is known as cryptography. The finer points are covered in this post and so I will not repeat them.

For the rest of this post, I will consider only public key crypto, wlog, as it is more intuitive to explain than private key crypto. Most crypto schemes are based on what are know as "number-theoretic assumptions." These are problems in number theory, which we believe are hard to solve. A security proof is generally done by a technique known as reduction. We assume that we can break our scheme using algorithm A and based on that, we show that we can construct another algorithm B which will solve the problem contained in our assumption. Since we know that it is hard to solve the problem in the assumption, then we we know it is also hard to break our crypto scheme. This is broadly called the standard model.

The choice of assumption is very important. There are some well known assumptions, which are accepted to be hard, such as the Diffie-Hellman problems and the RSA assumption. However, one can also introduce a new assumption provided it is accompanied with a proof of intractability (read hard to solve). The main point is there should be some proof that your assumption is intractable, which generally means that is an NP type problem. And that is where the connection lies.

If P = NP, then there exists a polynomial time solution for all NP problems, thus all our assumptions can easily be solved and thus all our encryption schemes can be broken. So, if P = NP essentially cryptography falls flat on its face, or does it?

Membership into the class P is determined by the bounds of the solution to a problem. The most common way of representing this is big-O notation. The problem with this notation is that it hides too much information for my liking. If we have two algorithms A1 & A2 for solving a problem A and we want to decide which is more efficient, we can compare the big-O notation. What do you do if both A1 & A2 are O(n^15) (where ^ denotes exponentiation). Both are polynomial in time, but one may be worse than the other by a factor of 100's or even 1000's. Another fact is that a problem may have a polynomial time solution, but the order of the polynomial may be so large as to make the computation infeasible e.g. O(n^100).

So, cryptography could possibly still survive a valid P = NP proof, but that is contingent on several factors. Most of it will be everybody disagreeing on what the limits are on feasible computation and what is truly secure and what is not.

As a final thought, as a cryptographer, you mostly have to believe that P != (read not equal) NP, which I strongly do.