P vs NP

So here is the first post, and it is a pretty interesting topic to start...

In the last couple of days rumours have spread around the internet about a mathematician from HP Labs, Vinay Deolalika, having proposed a proof of the conjecture that P does nto equal NP. This proof is currently being reviewed by the experts, and if it is proved to be correct then this will be the next of the Clay Institutes Millennium Prize problems to be solved.

So why is this interesting to at all, and why is it interesting to us cryptographers?

Firstly, as a purely financial justification; the Clay Mathematics Institute is offering a one million dollar prize for a proof of each of seven fundemental problems in mathematics. These seven problems were published in 2000 and consist of the following questions

1. P vs NP
2. The Hodge Conjecture
3. The Poincare Conjecture
4. The Riemann Hypothesis
5. Yang-Mills existence and mass gap
6. Navier-Stokes existence and smoothness
7. The Birch and Swinnerton-Dyer conjecture

Of these problems the Poincare conjecture is already solved (by  Perelman) in 2003, and of the other six I only really know about three: P vs NP (which I shall return to below), the Riemann Hypothesis (which is at the heart of problems about the distribution of prime numbers) and the Birch and Swinnerton-Dyer conjecture (which is about values of a function attached to an elliptic curve).

However, the P vs NP question is probably the most philosophically interesting. It basically asks whether it is easier to check a mathematical proof than it is to invent it. Intuitively this is born out by our experience in lectures; students find it easier to follow and understand a lecture than come up with the material from scratch on their own.

But it is not just a question about proofs. The two expressions P and NP refer to sets of problems. The set P is the set of problems for which we can decide whether they are true or false efficiently, i.e. in polynomial time (hence the P). These correspond, using the above analogy, to the problems for which we can come up with a proof efficiently. The set NP on the other hand is the set of problems for which given the problem and an additional piece of information called a witness (or proof), we can check the proof efficiently. Why this is called NP is technical and will not be gone into here.

The P vs NP question is whether the set P is equal to the set NP. It is clear that the set P is contained in NP, since we could take the witness to be empty for all problems in P. But if P does equal NP, then all sorts of things will follow: A lot of interesting problems for which we have no efficient algorithms could be efficiently solved. More importantly to us cryptographers, we would all be out of a job. Since all known practical encryption schemes are related to problems in NP.

Vinay Deolalika claims to have a proof that P does not equal NP. If his proof is found to be correct then this is great news for science in general, and cryptographers can breath a sigh of relief for a few more years. However, even if the proof is found to contain some errors it is likely to stimulate new ideas.

We are really living in interesting times