Blog: What Does 'P vs. NP' Mean for the Rest of Us?

What Does 'P vs. NP' Mean for the Rest of Us?
Technology Review (08/19/10) Pavlus, John

Although the current consensus is that Hewlett-Packard Labs research scientist Vinay Deolalikar's approach is fundamentally flawed, a verified P versus NP proof would conclusively determine what kinds of problems are and are not computer-solvable. NP-class problems in existence hold significant implications for pattern matching and optimization in a broad area of subjects. Such subjects include the arrangement of transistors on a silicon chip, the development of accurate financial prediction models, and analysis of cellular protein-folding behavior. The P versus NP problem queries whether these two classes are identical, which entails that every NP problem would feature a concealed shortcut permitting computers to rapidly come up with perfect solutions. Proving P is not equal to NP would validate widely accepted assumptions, such as the inability to efficiently factor massive composite numbers that form the foundation of modern cryptography. Still, "even if you proved that P does not equal NP ... it would have to radically expand our understanding of those capabilities, and make many new things possible with computers, in addition to all the clever workarounds we've already found," says Georgia Tech's Richard Lipton.

View Full Article