P vs. NP is one of the most famous and important problems in computer science. Informally: if the solution to a problem is easy to check for correctness, must the problem also be easy to solve? 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. The problem was included in the Millennium Prize Problems list published by Clay Mathematics Institute, the solutions to which will be awarded 1 million $ prize.
A good introduction to the problem is YouTube video "P vs. NP and the Computational Complexity Zoo" by hackerdashery.
Does P = NP?
If no award is given by the Clay Institute (between January 1, 2000 to January 1, 2100) for a proof or disproof of P = NP, this question will resolve ambiguously. The question will resolve ambiguously also if the problem is proven to not have a solution either way, e.g. if the problem will turn out to be unprovable or undecidable. If resolution is positive, the close date will be set retroactively to the date of complete initial publication (in journal or preprint form) of the proof, plus one year (or one day before the date of announcement of the prize, if that comes earlier.)
As some background, Gerhard J. Woeginger maintains a list of claimed proofs of the problem. As of 2018, the list contains 62 purported proofs of P = NP, 50 of P ≠ NP, 2 proofs the problem is unprovable, and one proof that it is undecidable. William I. Gasarch asked 100 various theorists the question whether P = NP. The result are as follows:
- 61 thought P≠NP.
- 9 thought P=NP.
- 4 thought that it is independent.
- 3 just stated that it is NOT independent of Primitive Recursive Arithmetic.
- 1 said it would depend on the model.
- 22 offered no opinion.