Blog: Prizes Aside, the P-NP Puzzler Has Consequences

Prizes Aside, the P-NP Puzzler Has Consequences
New York Times (10/08/09) Markoff, John

The frenzy of downloading that accompanied the September cover article in the Communications of the ACM when it was issued online reflects the intense interest in the subject of the article--the progress, or lack thereof, on solving the P vs. NP challenge. P represents the class of problems that can be solved in polynomial time, while NP represents the class of problems that can be confirmed in polynomial time. It is theorized that if P equals NP, some of the most complex real-world computing problems, such as optimizing the layout of transistors on a computer chip, could be addressed, triggering an acceleration of technological and economic productivity. Cracking computer codes raises a similar challenge. Such tasks share the common characteristic that an increase in the size of a problem is accompanied by an exponential increase in the computer time needed to solve it. Progress on meeting the P vs. NP challenge has been slow, but Lance Fortnow of the McCormick School of Engineering at Northwestern University believes the theory might be proved or disproved through algebraic geometry.

View Full Article