Whether P=NP is an unsolved problem in computer science. Informally, the problem asks if all problems whose solutions can be checked quickly can have those solutions found quickly. More formally, a collection of yes or no questions is said to be in P if there exists a Turing machine T, an integer k and constant C such that which will correctly answer whether the answer is yes or no, and the Turing machine will always terminate after a number of steps bounded by where n is the length of the input. A problem is said to be in NP if the same holds true for a non-deterministic Turing machine. It is not hard to see that any problem in P is also in NP. It is unknown if P=NP or not. This problem is one of the seven Millennium problems, for which each has a million dollar prize.
- Before consideration, a proposed solution must be published in a refereed mathematics publication of worldwide repute (or such other form as the SAB shall determine qualifies), and it must also have general acceptance in the mathematics community two years after. Clay Mathematics Institute
In August 2010, Vinay Deolalikar gave a proposed proof. MIT computer scientist Scott Aaronson was so confident that the proof is wrong, he’s offered Deolalikar an additional $200,000 if he’s awarded the $1,000,000 Clay Millennium Prize for the proof. The current consensus is that Deolalikar's proof does not work.