The
P versus NP problem is a major
unsolved problem in computer science. Informally speaking, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. It was essentially first mentioned in a 1956 letter written by
Kurt Gödel to
John von Neumann. Gödel asked whether a certain
NP-complete problem could be solved in
quadratic or
linear time. The precise statement of the P versus NP problem was introduced in 1971 by
Stephen Cook in his seminal paper "The complexity of theorem proving procedures" and is considered by many to be the most important open problem in the field. It is one of the seven
Millennium Prize Problems selected by the
Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution.