Sign In

Communications of the ACM

ACM News

What Does 'p vs. Np' Mean For the Rest of Us?

View as: Print Mobile App Share:
P vs. NP

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