dChan - Q Origins Project Archive

Tech policy

What Does ‘P vs. NP’ Mean for the Rest of Us?

A proposed “proof” is probably a bust–but even failed attempts can advance computer science.

John Pavlus archive page

August 19, 2010

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. It seeks to determine–once and for all–which kinds of problems can be solved by computers, and which kinds cannot. “P”-class problems are “easy” for computers to solve; that is, solutions to these problems can be computed in a reasonable amount of time compared to the complexity of the problem. Meanwhile, for “NP” problems, a solution might be very hard to find–perhaps requiring billions of years’ worth of computation–but once found, it is easily checked. (Imagine a jigsaw puzzle: finding the right arrangement of pieces is difficult, but you can tell when the puzzle is finished correctly just by looking at it.)

………….

https://www.technologyreview.com/2010/08/19/262224/what-does-p-vs-np-mean-for-the-rest-of-us/