For a few days, everyone in the field of computer science has been talking about the manuscript P ≠ NP published by Vinay Deolalikar from HP Research Labs on August 6, 2010. The 102-page manuscript on the P versus NP problem has taken so much attention from computer science researchers like Scott Aaronson, Greg Baker, and Dick Lipton.
Let’s see what Wikipedia says about P ≠ NP as a refreshment for the subject:
The relationship between the complexity classes P (Polynomial time) and NP (Nondeterministic Polynomial time) is an unsolved problem in theoretical computer science, and is considered by many theoretical computer scientists to be the most important problem in the field.
A proof that showed that P ≠ NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.
Yes, P ≠ NP is the expected answer, yet there is no accepted proof for that. It will be very interesting and lucky for us to witness an important milestone in computer science if Deolalikar’s claimed proof is found correct and approved by the computer science community. I think acceptance or rejection will take some time, and I’ll be waiting impatiently.
Update Jan 20th, 2011: Today I’ve seen a new work that claims P = NP with a Polynomial Algorithm for Boolean 3-Satisfiability Problem by Vladimir Romanov. http://romvf.wordpress.com/2011/01/19/open-letter/