P versus NP problem

The P versus NP problem is a major unsolved problem in computer science. Informally speaking, it asks whether every problem whose solution can be polynomially-time verified by a computer can also be polynomially-time 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.

An answer to the P = NP question would determine whether problems that can be verified in polynomial time, like the subset-sum problem, can also be solved in polynomial time. If it turned out that P ≠ NP, it would mean that there are problems in NP (such as NP-complete problems) that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields.

See also

Computer Complexity, Turing Machines, Theory of computation

Material

• http://www.claymath.org/millennium-problems

Papers

• Hartmanis, Juris. Gödel, von Neumann, and the P = NP problem. Bulletin of the European Association for Theoretical Computer Science 38: 101-107.