This week we’ve been lucky enough to have one of the biggest computer science stories break in recent memory, Dr. Vinay Deolalikar submitted a proof for the classic Complexity Theory problem of P ≠ NP. While this is ground breaking work, a colleague has suggested that it would it only be important if we could prove the opposite that P = NP.
I disagree with the statement on several points. I agree that proving P = NP would be the more interesting result, given that most OR and Computer Science practitioners I know believe that its the case that P ≠ NP. I list my reasons below that I think P ≠ NP is an important result
- It proves what is considered one of the top 6 outstanding questions in mathematics – While most of us may believe that P ≠ NP, none of us have been able to prove it and collect the $1 million Clay Millennium Prize for it, so if Dr. Deolalikar has done this he’ll be considered one of the greatest contributors to mathematics in our time.
- It puts math and computer science in the news – If this proof is accepted, with or without additional revisions, it will thrust our fields of study into mainstream news, all-be-it for a very short time, and that is good for all of us.
- It adds to our understanding of hard problems – Even if this attempt fails, Dr. Deolalikar has introduced some new ideas that will help all of us understand this class of problems better. This will lead to better understandings of algorithms and hopefully allow us to create better algorithms in the future.
- It encourages researchers – We all can use encouragement sometimes, and this would be a shot in the arm to researchers to continue to investigate really hard problems that some people think are impossible to solve.
Please feel free to leave anything I missed or that you disagree with in the comments.