HomeP vs. NP: a "million-dollar problem"
.jpg)
At the beginning of the century, the Clay Mathematics Institute launched the so-called Millennium Prize Problems: seven mathematical problems of great complexity and importance, whose resolution would bring great developments and technological advances. To encourage brilliant minds to address these problems, a million-dollar prize was offered. Among the several problems listed, one of them is extremely important in the world of optimization: the question of whether P is equal to NP.
Let's take a step back to better understand what these letters and this equation represent. To do this, we can define two classes of problems. Class P (deterministic polynomial time), comprised of problems that can be solved quickly, and where the difficulty grows slowly with the dimension of the problem; and class NP (non-deterministic polynomial time), whose solutions can be checked quickly. Therefore, the question is whether any problem whose solution can be verified quickly can also be solved quickly.
This question remains unanswered due to the fact that it has not yet been proven that there are problems whose solution can be verified quickly, but that the discovery of a solution cannot be determined efficiently.
Suppose you want to travel around Brazil and visit all 26 state capitals and the Federal District. When preparing the itinerary, you ask yourself a question: is it possible to make this trip covering less than 15,000 km? It is extremely difficult to answer this question since it would be necessary to test all possible route orders and calculate their distance. However, it is very easy to check if a given route can be covered with less than 15,000 km since it is enough to add the distance between the cities in the defined order. This problem is, therefore, NP, since a solution can be quickly verified, but it is not yet known whether it is also P, since it can't be quickly solved.
A third and important class of problems is called NP-complete: they are NP problems that can be transformed into other NP problems in polynomial time. For example, the problem of finding the best route to travel can be transformed into a problem of defining material loading with a certain value in a limited capacity container, such as the knapsack problem.
Knowing these classes of problems, and the types of problems they represent, we can have an idea of the consequences that solving this issue can bring. If someone proves that P is equal to NP, probably algorithms to quickly solve a complex problem, such as the best route to visit all Brazilian capitals, would be developed. By solving this problem, and knowing the characteristics of the NP-complete problems, a multitude of other extremely complex problems would also be solved, such as the resolution of classical industrial problems, allowing important discoveries, from new medicine for diseases such as cancer to the prediction of protein structure. There would also be serious consequences, such as encryption systems being deciphered, as their resolutions would become easy.
Proving the opposite, that P is different from NP, would also bring great benefits: it would allow better guidance in future research and a direction in computational complexity theory. For example, research on heuristics and meta-heuristics methods could be intensified, which seek to find good solutions, but do not necessarily guarantee optimality.
Therefore, the world as we know would be greatly impacted by any answer to this major problem. If you think you know how to answer if P = NP, don't waste time, because the millionaires' club is waiting for you!
Co-author: Fabio Silva - Senior Manager at Cassotis Consulting