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.
| Indicator | Value |
|---|---|
| Stars | ★★★☆☆ |
| Platform | Metaculus |
| Number of forecasts | 476 |
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...