assembling contingent understanding composing calibrated predictions generating quantitative estimations computing accurate estimations formulating intelligent futures mapping the future exploring probable forecasts crowdsourcing predictive understanding mapping probable contingencies forecasting accurate understanding modeling contingent understanding crowdsourcing accurate estimations forecasting accurate estimations formulating critical insights

Question

Metaculus Help: Spread the word

If you like Metaculus, tell your friends! Share this question via Facebook, Twitter, or Reddit.

Does P = NP? Informally: If the solution to a problem is easy to check for correctness, must the problem be easy to solve?

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.

The question asks:

IF the Millennium Prize is awarded for providing a correct proof during this century, will P = NP?

If no award is given during this century the 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.

{{qctrl.predictionString()}}

Metaculus help: Predicting

Predictions are the heart of Metaculus. Predicting is how you contribute to the wisdom of the crowd, and how you earn points and build up your personal Metaculus track record.

The basics of predicting are very simple: move the slider to best match the likelihood of the outcome, and click predict. You can predict as often as you want, and you're encouraged to change your mind when new information becomes available. With tachyons you'll even be able to go back in time and backdate your prediction to maximize your points.

The displayed score is split into current points and total points. Current points show how much your prediction is worth now, whereas total points show the combined worth of all of your predictions over the lifetime of the question. The scoring details are available on the FAQ.

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.

This question is not yet open for predictions.

Thanks for predicting!

Your prediction has been recorded anonymously.

Want to track your predictions, earn points, and hone your forecasting skills? Create an account today!

Track your predictions
Continue exploring the site

Community Stats

Metaculus help: Community Stats

Use the community stats to get a better sense of the community consensus (or lack thereof) for this question. Sometimes people have wildly different ideas about the likely outcomes, and sometimes people are in close agreement. There are even times when the community seems very certain of uncertainty, like when everyone agrees that event is only 50% likely to happen.

When you make a prediction, check the community stats to see where you land. If your prediction is an outlier, might there be something you're overlooking that others have seen? Or do you have special insight that others are lacking? Either way, it might be a good idea to join the discussion in the comments.