Big and beautiful problems will be solved

p vs p

Status: Unresolved since 1971

what’s the problem ?

The problem of “P vs NP” crosses the mathematical boundary and falls into the domain of computer science. We can summarize it by saying that it is a question of measuring the speed of an algorithm. So what do P and NP mean? In computer logic, these characters designate two classes of complexity of a problem. And the whole question is whether or not “P = NP” is true, or whether it is impossible to prove it.

Let’s take a concrete example to simplify this problem. We are used to finding quick solutions to very complex problems. You don’t need to be a musician to know if the score is perfect, or to be a cook to enjoy a dish. Whereas if you are asked to prepare a recipe or write a score, the difficulty will be much greater. “P = NP” refers to the question: Is finding a solution as difficult as verifying it? The problem was formulated in 1971 by Stephen Cook (left) and Leonid Levin (right).

Why is it so complicated?

As we can see, the problem of P = NP is almost as mathematical as it is philosophical! It touches on one of the foundations of human reasoning, namely our ability to quickly recognize right and wrong in the face of our intuitive understanding of solutions. Of course, in mathematical terms, the question is completely different. The class P is defined as the problems that can be solved in so-called polynomial time (proportional to the size n of the problem) using a deterministic algorithm. However, until now, no one has been able to apply this well-known algorithm to NP, especially for the so-called NP-complete class.

Ways to solve it: Minor!

Richard Kaye of the University of Birmingham, England, has brought a playful lead on problem solving. It’s about using … Minesweeper game! This classic of pre-Internet entertainment, present on many versions of the Windows operating system, makes it possible to deal with the problem. In this game we have to find where the mines are hidden on the wide grid. By randomly choosing the first one, either we explode, or we find clues on the position of the next (using numbers to indicate how many adjacent squares have a mine). Its logic can be translated into mathematical terms to facilitate the understanding of P = NP.