P = NP is a major unsolved problem in Computer Science. Regarding the recent attempt to solve it this problem by Vinay Deolalikar (August 6, 2010), in this post we will briefly review what is this about P = NP, consequences if that statement is true, why many people was so excited over the possible solution announced recently, and some interesting observations on how our society reacted to it. The answer to this question seems to be P!=NP and it looks like the recent Vinay's proof is not correct. Moreover, it has some issues that make it hard to fix.
What P and NP means?
Given a problem, first we want to discover candidate solutions and then verify them. The goodness of these discovering and verification tasks commonly depend on the use of limited resources such as time and space. Thus, the time employed to discover a solution (or to verify it) can be efficient or inefficient. Having said that, P and NP are sets of computational problems. A P problem can always be solved in polynomial time in the size of the input. A NP problem can always be quickly verified in polynomial time. NP problems are interesting because although they can be quickly verified, they may not be quickly solved. Hence, P is always included in NP.
However, stating that P = NP means that all problems are both quickly solved and verified. If you find a problem difficult to solve, there will be a theoretical guarantee that there exists a efficient (at most polynomial) way to solve it. If you are trying to solve your Sudoku, you can be confident that there is an efficient way to solve it, even if you cannot find it. Here, we are not considering NP-hard problems, which are those whose verification is not polynomial.
What made Vinay's attempt special this time?
This is a good question. To frame the discussion, people propose proofs that P = NP or P!=NP all the time. For example, in arXiv.org you can easily find recent attempt to show one of those statements (http://arxiv.org/find/all/1/all:+AND+proof+AND+p+np/0/1/0/all/0/1). Thus, this is not a sporadic effort to solve this problem, it is a well-studied theoretical problem with many people trying to solve it. Why this time the propagation of this news was so fast then?. Here are my hints:
- The way how Vinay introduced his work to the community was unusual. Unlike the traditional way used in academy, where the submission/acceptance of a paper after a peer review process is the rule, he sent the manuscript to 22 experts in the field and they quickly realized a valid attempt to solve this problem.
- The method employed by Vinay was novel. The use of random k-SAT was a path that few people traversed before. If there is a solution to this problem, many people agree that it should consider the problem from a new perspective. After all, this is an old problem and many well-known techniques has shown to fail to prove P=NP.
- Internet time. It is now easier to receive news and share our own impressions. The proof provided by Vinay was made public and he received feedback the next day he sent his work. This is a summary.
August 6, Document sent to 22 people
August 7, Greag Baker's blog post "P != NP"
August 8, Slash dot
August 9, Wikipedia article about Vinay. Richard Lipton wrote a post "Issues in the proof that P != NP"
August 10, First discussions to create a Wikipedia article about Vinay's attempt to solve the problem (340 edits so far)
August 11, Wikinews: "Researcher claims solution to P vs NP math problem"
August 15: Richard Lipton blog posts saying that proof seems incorrect
August 17: Author said the paper was sent out for refereeing
The paper was less than one-week-old and it already produced blog posts and technical discussions in Wikipedia, Wikinews, and Slashdot. After one week the proof seemed to show some issues and people, including Vinay, tried to fix those problems to see if it could solve P=NP. This seems to indicate that although complex knowledge is currently fragmented, now we can collaborate in a very short time such that someone can ask a complex question and receive meaninful feedback very soon.
Comunity refereeing
Now the propagation of news is faster than anytime before. Once those 22 experts received the work, they spent time to analyze it. The manuscripts was made public by the author and many people around the world also read it, some of them discovered interesting issues in the proof and provide nice counter examples. I wonder whether we we in front of a new model to review academic works. Is community refereeing better than the traditional peer review process?..
Finally, I would say that Vinay did the right thing. He made an interesting work, discussed it with his colleges, send the work to experts within the field, received the feedback, and sent the work for publishing. Even if the proof results to be rejected, his work should be recognized. Everyone agrees that it is easier to verify the validity of an academic work than to solve it. Unless someone proves P=NP :).
(*) Thanks to Kenneth Clarkson, Ronald Fagin, and Ryan Williams at IBM Almaden Research Center for their wonderful talk. It was a nice way to get insight on the proof and understand its applications on real problems like databases and cryptography. Ron was one of the 22 that initially received the work for its consideration.
