Non Deterministic Polynomial Problems

It is comfortable to think that we are living in the golden age of technology and science, whose solutions to the main problems are already in our hands, or that we are only a few years away from achieving them. Unfortunately, this is not true; our universe is filled with questions that we human beings are still unable to answer. Before getting into the subject of the post, I will make a brief delirium of where we are today from my point of view.

To be honest, our understanding of nature is so limited that all we can do is find and study cause -effect correlations. We still don't have the fundamental understanding of what physics really is, for example, or what the objects that pervade us are actually made of or how they came to be. I'll make an analogy to try to clarify my reasoning: through observations, we know that an object will fall if we drop it from a high place and, through hypotheses, theories, research and experiments, we associate the fall of this object with gravity; today, we also understand, using the same methods, that gravity is related to the mass of objects and that the denser and heavier this object is, the stronger the gravitational force exerted. But why does this happen? We don't know what gives shape to matter and why it generates this force; or is it not matter that “emits” gravity, but something that we are not yet aware of? We managed to go further and propose that gravity is nothing more than an effect caused by the way matter is built and correlated with the fabric of space and time, so studying gravity as a force only makes sense in physics books. Mathematics, physics, and any other subject are human inventions; from them, we try to make sense or find a way to explain what we don't really understand.

We can extrapolate this analogy to any technology and innovation that we develop to mitigate our problems and make our lives easier and more comfortable, since the scientific method itself is based on the pillars of "observation", "hypothesis" and "experimentation". Don't get me wrong, this scientific method has been helping us a lot so far and it is through it that we managed to evolve to where we are today, however, there is a limit and risk associated with this methodology. From an observation, theories and hypotheses are formulated that can be proven or not when the results of experiments are analyzed; a scientific fact today may well be discarded if another better explanation for a given observation is proposed. Even the advanced medicines and treatments that we enjoy today were gained through observation; to corroborate this, it is enough to remember that a part of the medications are found “by chance”.

Let's step into the world of science fiction a little now and ask ourselves what would humanity be like if we managed to find the answers to these fundamental questions? Where would we be if we were able to answer all the "whys" there is to answer? Except for this brief moment of reflection, let's get into the subject of the post. I hope I didn't bore the reader too much.

One of the reasons for our limited, almost blind, understanding of nature is the computational power available today which, despite not appearing to be, is still the main bottleneck for many studies, holding researchers back from the most important advances we need to achieve. Even the most powerful supercomputer that humanity has produced, the Fugaku, is not enough to get quick answers to common problems that need to be answered by researchers and scientists. Therefore, the scientific community has organized the thinking, classifying the problems in such a way that "optimization" of algorithms is one of the fundamental pieces of the puzzle. These classifications, in short, are the “P”, “NP”, “NP Complete” and “NP Hard” type problems. There are other subclassifications, but my knowledge is limited to understanding these and, even so, superficially.

"P" represents a class of problems that can be solved by reasonably fast algorithms, where "P" stands for "Polynomial Time". In other words, this means that we can find the solution to problems "P" in polynomial time, and as a given problem gets more complex, the time to find the solution increases according to a polynomial function, not an exponential one. For example, the multiplication of numbers itself is a class "P" problem, as there are computational algorithms that solve multiplication in a timely manner; the larger the numbers to be multiplied, the more complex the problem is to solve and, consequently, more computational power and time are needed to find the answer. However, this time increase follows a “straight line” on a time x number size graph. Other examples of type "P" problems:

· List organization: how to put all elements of a list in alphabetical or ascending order.

· Mazes: how to find the way out of a maze given a starting point.

· Rubik's Cube: How to arrange the cube so that all sides are the same color.

We also have problems of the “NP” type, in which “NP” stands for “Non-Deterministic Polynomial Time”, these problems being those that, given a correct solution, it is possible to verify if this solution is correct with algorithms that run in a timely manner, but on the other hand, it is not possible to find the solution of a “NP” problem with acceptable speed. A common misconception is that the acronym "NP" stands for "non-polynomial" when, in fact, it stands for "non-deterministic polynomial problems", as the algorithm for finding prime numbers, vehicle routing and project / manufacturing activity sequencing are some examples of "NP" type problems.

A "NP" problem can become a "P" problem if some researcher manages to develop an optimal computer program that solves this problem quickly, in polynomial "P" time. There is a hypothesis that says that at some point in the future, all "NP" problems will become "P" problems, however we are not there yet (in fact, we don't know if we ever will). This hypothesis is then defined by the question: “Does being able to quickly test a solution mean that there is also a quick way to find the solution?”. However, to date, no one has been able to prove this hypothesis.

To better understand the difference between "P" and "NP", let's use Sudoku; today, the best computational algorithms developed to find the solution of a Sudoku still takes a long time to calculate the correct answer, and the more complex the Sudoku, the longer it takes to find the answer, which increases following an exponential function (not “P"); however, given that we have the solution for this Sudoku, it is possible to know if this solution is correct or not using existing programs that are reasonably fast.

Another class of problems, the "NP Complete", are problems of the "NP" type, but their solutions are such that, once one of these problems can be solved in "P" time, all other problems of the type "NP" can also be solved with the same solution or modifications of this algorithm. As examples of “NP” problems, we have the Tetris, Naval Battle, Crossword and Sudoku games, in addition to the classic scientific problem of Protein Folding. Looking at these examples, we can understand that if someone develops an algorithm that finds the solution to Sudoku in polynomial time, so that this problem is no longer categorized as "NP" and becomes categorized as "P", every other "NP" type of problems can use this solution. That is, the researcher who manages to develop a computer program that solves any Sudoku, whether simple or complex, in polynomial time, he will be helping to find a cure for cancer, for example, since these cures depend on solving “NP” problems, like Protein Folding.

The last class that we will cover in this post is the “NP Hard”, which are problems whose solution is minimally as complex as the more complex “NP” problem. In computational complexity theory, “NP Hard” (non-deterministic polynomial hardness) is the defining property of a class of problems that are informally known to be "at least as difficult as the most difficult problems in 'NP' (non-deterministic polynomial time). A more precise specification is: A problem H is “NP Hard” when every problem L in “NP” can be reduced in polynomial time to H; that is, assuming that a solution to H takes 1 unit of time, the solution to H can be used to solve L in polynomial time. Therefore, finding a polynomial-time algorithm to solve any “NP Hard” problem would provide polynomial-time algorithms for all problems in “NP”; and it is unlikely that such an algorithm exists, as mentioned earlier. Furthermore, the class “P”, in which all problems can be solved in polynomial time, is contained in the class “NP”.

The schematic below represents the problem sets “P”, “NP”, “NP Complete” and “NP Hard”, with the schema on the left assuming that the answer to the question “Being able to quickly test a solution means that is there a quick way to find the solution?” is “no”. The schema on the right assumes that the answer to this question is “yes”: