Millennium Problems

In the year 2000, a private research institute in the USA, the Clay Mathematics Institute, published a list of seven tasks. All seven are questions from mathematics on which experts have failed for over a hundred years in some cases. For each complete and verified solution, one million US dollars is offered. Since then, these tasks have been called the Millennium Problems, named after the turn of the millennium. To this day, only one of them counts as solved: the so-called Poincaré conjecture, a question about the shape of spaces. The Russian mathematician Grigori Perelman solved it in 2003 and declined the prize money.

Seven questions on which cryptography and computer science depend

The list is not a ranking of the hardest puzzles for fun. The questions were chosen because their answers would reshape entire fields. Whoever solves them delivers not just a result, but usually also new methods. It is precisely these methods that are the real prize.

For the tech world, one of the problems is especially explosive: the question of whether P equals NP. Behind this lies the question of whether every task whose solution can be checked quickly can also be found quickly. A Sudoku is checked in seconds but hard to solve. Almost all experts suspect that solving is truly harder than checking. This has not been proven.

If the answer turned out to be surprisingly yes, it would have consequences for encryption on the internet. Online banking and messenger messages are protected because certain computational tasks appear practically unsolvable. If this assumption fell, security technology would have to be rebuilt from the ground up. The Riemann hypothesis, a question about the distribution of prime numbers, also touches this field directly.

What counts as a solution

A Millennium Problem does not count as solved through a good idea, but through a proof. A proof is an unbroken chain of justifications that leads from accepted basic assumptions to the result. Computational examples are not enough. Even a million confirmed individual cases prove nothing about the infinitely many remaining ones.

The institute has fixed rules for awarding the prize. A paper must first appear in a respected specialist journal. Then two years must pass, during which other researchers can examine and attack it. Only after that can a committee release the prize money. This detour protects against errors that are invisible at first glance.

In practice, very many alleged solutions are submitted, almost always by outsiders. Nearly all contain a flaw in reasoning at a point that seems harmless at first sight. With Perelman’s proof, several teams of experts needed years just to fully verify it.

Why the term appears in tech headlines

In the news, one encounters the Millennium Problems mostly in two contexts. The first is encryption: reports about quantum computers often mention that today’s security methods rest on unproven assumptions. The second is artificial intelligence. Again and again it is reported that an AI system has cracked a mathematical problem or performed well in a competition.

Such reports are worth a closer look. AI systems today can solve tasks at the level of school olympiads and help experts with partial steps. No Millennium Problem has been solved by one so far, not even close. Between a hard competition task and a problem open since 1859 lie worlds of difference.

Another trend is interesting: proof assistants. These are programs that check every step of a proof for consistency. Increasingly, new proofs are being formally stored in them so that machines can verify them. Should a Millennium Problem ever fall, the verification will presumably take place using such software.