P Versus NP
The question is whether, for all problems for which an algorithm can verify a given solution quickly (that is, in polynomial time), an algorithm can also find that solution quickly. The former describes the class of problems termed NP, whilst the latter describes P. The question is whether or not all problems in NP are also in P. This is generally considered one of the most important open questions in mathematics and theoretical computer science as it has far-reaching consequences to other problems in mathematics, and to biology, philosophy and cryptography (see P versus NP problem proof consequences).
- "If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in 'creative leaps,' no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss..."
- — Scott Aaronson, MIT
Most mathematicians and computer scientists expect that P≠NP.
The official statement of the problem was given by Stephen Cook.
Read more about this topic: Millennium Prize Problems