Recent P != NP excitement & activities

P = NP or P != NP is an important and fundamental problem in mathematics and computer science. Vinay Deolalikar, a research Scientist at HP Labs, has circulated a paper that he thinks prove P != NP (see an older version here). Some researchers in the field have pointed out some general issues (fatal?) and created a really impressive wiki about Vinay’s paper to track and document the various discussions for the public to try to follow. Cool stuff.

Love this quote,

We think that Vinay Deolalikar should be thanked for thinking about this difficult problem, and for sharing his ideas with the community. Whether he got it right or not, he has tried to add to our understanding of this great problem. We need more people working on hard problems. If no one does, then they never will be solved.

On a personal note, I love to see P =? NP resolved in my life time since my first exposure to the problem in 1990 in Prof. Stephen Cook‘s undergrad computation complexity class at U of T. My sense this morning is that Vinay may not have cracked the problem yet, I do hope he or other researchers (individually or as a team) will finally crack it. Good luck to them all.

[HT Schneier Gomes]

P.S. Incidentally, Michael Nielsen (the person hosting the above wiki) is working on a book, to be published by Princeton University Press in 2011, that describes both the great potential of online collaboration tools “to improve how science is done, and the challenges that must be overcome to fully realize that potential”. A preview of some themes of his book may be found in his essay about The Future of Science.

I also noticed this interesting wiki for “polymath projects – massively collaborative online mathematical projects“.


Comments are closed.

%d bloggers like this: