The are several problems in computer science that people are trying to solve all the time, many of these problems tie into mathematics or other areas. Wikipedia has a good list of currently unsolved problems, with links to descriptions and more information for those interested.
The problem of interest to this blog post is the first such problem mentioned on that page: P = NP?
AOL News has an article that I feel explains the problem much better than the Wikipedia page does for people who are not as fluent in their math as I'd like to be (you can find the complete article here). Quoted from said article:
Roughly, the mathematical problem asks if "questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure," according to the Clay Mathematics Institute.
This may not adequately describe the problem to you, but if you're interested in more information on the problem itself, I direct you again to the article and also to the Wikipedia page on P versus NP.
My reason for not explaining the problem better here is twofold. First, I do not believe I can explain it better than those sites do. Second, my purpose for writing this is not to explain what the problem is, but to share a bit of news on the problem.
Now that we have that out of the way, on to the news!
On August 6th, e-mails were sent to several researchers from Dr. Vinay Deolalikar. Dr. Deolalikar is the Principle Research Scientist at HP Labs. In this e-mail, he explained to his fellow researchers that he has found a solution to this problem, and also shared with them his findings in a paper.
This paper was leaked onto the web, in pdf form (can be found here). The 66 page document has been shared across the internet by now, but is not the end of the story. Today, Dr. Deolalikar released a longer, updated form of the paper (102 pages, here). He has also stated that the final form of the paper is still under work, and will be released shortly.
This may not sound like such a big deal to some of you, but I assure you, this may be the most important computer science problem currently, and if this answers the problem, it is an amazing piece of research. The P vs. NP problem is one of the Millennium Problems and solving it has a prize of $1,000,000. Yes, one million dollars to whoever solves this problem, or any of the other Millennium Problems, it is that big of a find.
Currently it can be assumed that hundreds, if not thousands, of mathematicians and computer scientists, professional and armchair alike, are poring over the paper looking to see if there are any issues with it and to determine if it is correct. I for one find it way over my head, as I had to pull out a dictionary during the first paragraph of the abstract, but I still find it exciting that a solution may have been found.
Links
HP Labs: Vinay Deolalikar
AOL News: P=NP=WTF?: A Short Guide to Understanding Vinay Deolalikar's Mathematical Breakthrough
Greg and Kat's Blog: P ≠ NP
The P Versus NP Page
Wikipedia: P and NP
The Millennium Prize Problems
The Early, Leaked Version of the Paper (66 pages)
Updated Version of Paper (102 pages)
No comments:
Post a Comment