Thursday, August 12, 2010

P versus NP

I have seen a lot of positive buzz around the fascinating P versus NP problem. It is so fascinating that I decided to study it deeper during my master studies. For those unfamiliar with this area, this is the major unsolved problem in Computer Science. It's so important that there is one USD 1 million prize for the one who solves it!

The buzz is due to a recent paper from Vinay Deolalikar. I've not read the paper and honestly I don't think I have enough background for it. This seems to be a very complex work. From a quick read over the Introduction, the author says that theories from several apparently unrelated areas are used throughout the proof: logic, statistics, graphical models and others. And the proof claims that P!=NP.

It's important to notice that several other researches have tried to solve the P versus NP problem. Take a look at this page if you wanna know more about it:

See you!

No comments:

Post a Comment