P versus NP

Some tasks are hard to solve but easy to check. Filling in a Sudoku can take hours. Checking a completed Sudoku takes a minute. This exact gap lies at the heart of the P versus NP question. P stands for the tasks a computer can solve quickly on its own. NP stands for the tasks where it can at least quickly verify a completed solution. The open question is: Are these actually the same tasks? For over fifty years, nobody has been able to prove or disprove this.

What hinges on this one question

In the year 2000, the Clay Mathematics Institute declared the question one of the seven Millennium Prize Problems. A proof carries a reward of one million US dollars. But the money is the smallest part of its significance. Practically all digital security rests on the silent assumption that P and NP are not the same.

When you establish an encrypted connection in your browser, calculations are often performed with very large numbers. The security rests on the fact that nobody can quickly factor these numbers into their components. Checking, by contrast, is trivial: you multiply the factors and see if they match. If P equaled NP, there might be a fast method for cracking these numbers. Online banking, passwords, and digital signatures would have to be rethought.

The other side of the coin, however, would be a blessing. Many important optimization tasks belong to NP: scheduling, route planning for delivery fleets, protein folding in drug research. A fast general-purpose method would make these problems solvable at a stroke. Most experts, however, consider this unlikely. In surveys of researchers, a large majority bets that P and NP are different.

Solving quickly versus checking quickly

“Fast” has a precise meaning here. Computer scientists look at how strongly the computing time grows as the task gets larger. If it grows at most as a power of the input size, that counts as fast. This is called polynomial time, which is where the P comes from. If, on the other hand, the time doubles with each additional element, the task becomes practically unsolvable even at moderate sizes.

NP encompasses all tasks for which a proposed solution can be checked in polynomial time. Every problem in P is automatically also in NP, because whoever can compute quickly themselves can certainly also check quickly. The only question is whether NP additionally contains tasks that don’t also fall into P.

One tool makes the matter manageable: NP-complete problems. These are the hardest cases in NP, and they can all be translated into one another. If someone finds a fast method for even one of them, all the others fall along with it. This group includes the traveling salesman problem and many puzzles like generalized Sudoku. The fact that, despite decades of searching, no fast method has been found for any of them is the strongest evidence against P equaling NP. It is not a proof.

Where you run into this problem in everyday life

The most common contact point is encryption. Every lock icon in your browser’s address bar represents a method based on calculations that are hard to reverse. The topic also comes up in the debate about quantum computers. An important distinction is needed here: quantum computers would not resolve P versus NP. They are faster at certain specialized tasks, such as factoring large numbers, but nobody expects them to crack all NP problems.

In software practice, you constantly run into NP-complete tasks without anyone naming the term. A delivery service planning routes isn’t looking for a perfect route. It settles for a good approximation that’s ready in seconds. Scheduling tools for school timetables or chip layouts work exactly the same way. Foregoing the optimal solution is a direct consequence of this theory.

The term shows up in the news whenever someone announces a proof. This happens regularly, and so far none of the attempts has withstood scrutiny. A widespread misconception is also that AI could simply sidestep the question. A language model only guesses good candidates. It doesn’t turn a hard task into an easy one.