Communications of the ACM
What Does 'p vs. Np' Mean For the Rest of Us?
Technology Review
Programmers and computer scientists have been buzzing for the past week about the latest attempt to solve one of the most vexing questions in computer science: the so-called "P versus NP problem."
Vinay Deolalikar, a research scientist at HP Labs in Palo Alto, CA, posted his "proof" online and sent it to several experts in the field on August 6. Colleagues immediately began dissecting the proof on academic blogs and wikis. Early reactions were respectful but skeptical, and the current consensus is that Deolalikar's approach is fundamentally flawed.
A solid proof would earn Deolalikar fame and fortune. The Clay Mathematics Institute in Cambridge, MA, has named "P versus NP" as one of its "Millennium" problems and offers $1 million to anyone who provides a verified proof.
But "P versus NP" is more than just an abstract mathematical puzzle...
From Technology Review
View Full Article
No entries found