Can every solved problem whose answer can be checked quickly by a computer also be quickly solved by a computer? P and NP are the two types of maths problems referred to: P problems are fast for computers to solve, and so are considered “easy”. NP problems are fast (and so “easy”) for a computer to check, but are not necessarily easy to solve.
In 1956, Kurt Gödel wrote a letter to John von Neumann. In this letter, Gödel asked whether a certain NP complete problem could be solved in quadratic or linear time. In 1971, Stephen Cook introduced the precise statement of the P versus NP problem in his article “The complexity of theorem proving procedures”.Today, many people consider this problem to be the most important open problem in computer science.[](https://simple.wikipedia.org/wiki/P_versus_NP#cite_note-3) 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.
There are many important NP problems that people don't know how to solve in a way that is faster than testing every possible answer. Here are some examples: