Your submission is now in Draft mode.

Once it's ready, please submit your draft for review by our team of Community Moderators. Thank you!

Submit Essay

Once you submit your essay, you can no longer edit it.

Pending

This content now needs to be approved by community moderators.

Submitted

This essay was submitted and is waiting for review.

P = NP is True

Question

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:

  1. 61 thought P≠NP.
  2. 9 thought P=NP.
  3. 4 thought that it is independent.
  4. 3 just stated that it is NOT independent of Primitive Recursive Arithmetic.
  5. 1 said it would depend on the model.
  6. 22 offered no opinion.

Make a Prediction

Prediction

Note: this question resolved before its original close time. All of your predictions came after the resolution, so you did not gain (or lose) any points for it.

Note: this question resolved before its original close time. You earned points up until the question resolution, but not afterwards.

Current points depend on your prediction, the community's prediction, and the result. Your total earned points are averaged over the lifetime of the question, so predict early to get as many points as possible! See the FAQ.