How do you explain to outsiders a subject your own mind can barely grasp? Our developer Max suggested the topic “P versus NP” – we'll give it a go.
What are the millennium problems?
The millennium problems are seven unsolved problems in mathematics listed by the Clay Mathematics Institute in 2000. A prize of one million US dollars is offered for solving each of them. So far only the Poincaré conjecture has been solved – and the Russian mathematician Grigori Perelman declined the prize money.
What is the P-NP problem?
The question is: is the class of problems that can be solved quickly (P) identical to the class of problems that can be checked quickly (NP)?
The knapsack analogy
Imagine you are planning a hike and have to pack your rucksack. Whether the items fit is easy enough to answer. But which combination is optimal? That is a typical NP problem.
Why does it matter?
If P = NP held, it would be a breakthrough: cryptography would collapse, but many optimisation problems in AI and logistics would also become solvable. If P ≠ NP holds, there are fundamental limits to computing power.
