The Explainer: P vs. NP

The Clay Mathematics Institute has a standing offer of $1 million for anyone who is able to prove or disprove one of seven problems that have never been solved. One of those problems is P=NP. Essentially, P is a set of relatively easy problems, and NP is a set of what appear to be extremely hard problems, so P=NP implies that the apparently hard problems actually have relatively easy solutions.

In a 2002 poll, 61 mathematicians and computer scientists responded that they believed P probably did not equal NP, and only nine did, and of those nine several admitted that they took that position just to be contrary.

Massachusetts Institute of Technology professor Michael Sipser, a member of the Computer Science and Artificial Intelligence Lab Theory of Computation Group, says the P-versus-NP problem is important to advancing the understanding of computational complexity and could have a major impact in cryptography. "The P-versus-NP problem has become broadly recognized in the mathematical community as a mathematical question that is fundamental and important and beautiful," Sipser says. "I think it has helped bridge the mathematics and computer science communities."

From MIT News
View Full Article

Abstracts Copyright © 2009 Information Inc., Bethesda, Maryland, USA