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.

P=NP

Recently, a friend of mine pointed me to this possible solution to P vs. NP. Just to jog your memory, here's $20 (I know, it's a terrible joke and I apologise.) On a serious note, here is my previous post on the same problem. Now the key difference between the previous proof and this one is the result. Where as Vinay Deolaiker tried to show P != (read not equal) NP, Vladimir Romanov has tried to show P = NP.

In my last post, I didn't really cover the problem itself. As promised I will do so in this post. The P vs. NP problem is a problem in computational complexity, which I will explain at a very high level. The class P is of those problems which can be solved in polynomial time, which is conisdered to be analogous to efficient. These problems are considered "easy to solve." The class NP is problems which cannot be solved in polynomial time, but in superpolynomial time or worse. These problems are considered hard to solve. There is a bit more mathematical finesse to the whole problem, but this basic concept is sufficient for now.

The whole P vs. NP debate is based on the relationship between P and NP, i.e. is P = NP. If P = NP this means there exists a polynomial time (read efficient) solution to all NP problems. This doesn't tell us anything about the solutions for the problems, other than that they exist. If P != (read not equal) NP, then all NP problems cannot be solved in polynomial time (read efficiently.) There is a whole issue about problems being misclassified as NP, but we omit that as it is not necessary for this discussion.

What was discovered is that some NP problems, that can be written as another NP problem, known as reducing. An overly trivial example is how multiplication can be written as addition e.g. 3 x 7 = 7 + 7 + 7. Neither addition nor multiplication is NP, but the example will help you visualise the concept. Following this discovery, was the realisation that all other problems in NP could be reduced to certain other problem, which is known as NP-completeness. That is a problem is NP-Complete if all other NP problems can be reduced to it. All reduction to an NP-complete are polynomial in time (just trust me on this one.)

Now, this leads us to the basic structure of pretty much all P = NP proofs: A polynomial time solution problem to a NP-Complete problem. The logic is simple if there exists a polynomial time solution to problem C, then there exists a polynomial time for all NP problems P. To achieve this, we reduce P to C (which is polynomial in time) and then solve C (which is again polynomial.) A polynomial plus a polynomial is still a polynomial. Thus, all NP problems have a polynomial solution, which implies they are in P. Therefore P = NP QED.

Now, back to Romanov's proof. He has proposed a polynomial time solution for what is know as 3-Satisfiability or 3SAT. If you are unfamiliar with this problem read the Wikipedia entry on it for the basic idea. One of the most remarkable things about his proof, is that he has implemented it and released the code for it, available here. Some proofs, although efficient in theory, can not be realised in practice due to various implementation issues. Here what we have is not only a theoretical result, but a practical implementation of it as well, which is quite an achievement.

Now, on the the actual proof itself. After a first reading of this paper, I was fairly convinced that the proof is valid an will hold. But therein lies my folly. I then proceeded to properly read the paper and understand the proof and evaluate if it was valid or not. My evaluation would not be the best, but it would be a start. As I went on through the paper, I noticed something very disconcerting; some of the key points were not, in my opinion, explained well enough. Everything is explained, but some key points lacked sufficient detail, enough so as to make them seem more akin to magic than math.

Everything seems to check out, but as there is not enough detail on some of the main points, I am inclined to disregard this as a valid proof. Of course, I could be wrong, but that is up to domain experts to decide. I am tracking this story fairly closely and will post any updates I find. I'm sure you are wondering, "Why do you even care?" Very good question, which is shall explain in a future post.

P vs. NP goes on

So if you remember, I wrote about a proof to the P vs. NP problem proposed by Vinay Deolalikar. Well, it turns out there are "fatal flaws" in his proof, thus rendering it invalid. So, unfortunately he can no longer get the Millennium Prize or the Fields Medal for this proof. However, he has provided a brand new way of looking at the problem and has no doubt inspired many researchers to follow his methodology or indeed even improve on it. Until then, we wait. It's been over a century, a couple more years can't really hurt.

P vs. NP solved?

Again, I have been away for a while. I have been engulfed in my Master's Thesis (will possibly post that up as soon as its finished), which is taking up all my time. Despite that I had to come here and write a quick post about this (It will not be to my usual standard because it is rushed). Apparently we have a solution to a Millennium Problem. Just for those who are unaware, the Clay Institute of Mathematics set up the Millennium Problems, which are 7 open questions in Mathematics. These are not just any questions, but problems that have remained unsolved for hundreds of year. These are the hardest problems in Mathematics.

Previously, A proof of The Poincaré conjecture has be presented by Grigori Perelman, a Russian Mathematician. He did in fact refuse the $1M prize that goes with the Fields Medal, but the point remains, he was the first to solve a Millennium Prize Problem.

Of the 6 remaining, a proof has now emerged to the P vs. NP problem. Vinay Deolaiker of HP Labs has presented a proof that P !=(read not equal) NP. This Prof, if correct will have a massive effect on several areas of mathematics, but especially computer science and indeed cryptography. The proof is said to be 100 pages, but I cannot confirm nor deny this. I have not yet read it, but it is bound to be long. It is currently undergoing peer review, i.e. being checked and rechecked from very angle and being torn to bits by other Mathematicians.

I will try and keep you apprised of the developments and post more details about the problem and solution when i have time. Promise.

*EDIT*
So, If you follow the Link below in the comment posted by Jack, you will see some of the potential flaws in the proof. These may or may not hold and are being raised and addressed to check that the proof is robust. It may also be that there is a problem with the proof and it does not hold in its current form, but may hold with some modifications. As said before, time will tell.