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.