It’s easy to believe that we are living in the golden age of technology and science, with solutions to the world’s greatest problems already in our hands, or just a few years away. Unfortunately, this is not the case. Our universe is filled with questions that humanity still cannot answer. Before diving into the topic of this post, I’d like to share a brief reflection on where we stand today, from my perspective.

To be honest, our understanding of nature is so limited that all we can do is find and study cause-and-effect correlations. We still don’t have a fundamental understanding of what physics truly is, for example, or what the objects around us are made of or how they came to be. Let me make an analogy to help clarify my point: Through observation, we know that an object will fall if we drop it from a height, and through hypotheses, theories, research, and experiments, we have linked this fall to gravity. Today, we also understand that gravity is related to the mass of objects, and that the denser and heavier an object is, the stronger the gravitational force it exerts. But why does this happen? We don’t know what gives matter its shape or why it generates this force. Could it be that matter itself doesn’t emit gravity, but rather something we’re not yet aware of? We’ve gone further by proposing that gravity is simply an effect caused by how matter interacts with the fabric of space and time. Studying gravity as a force only makes sense within the confines of physics books. Mathematics, physics, and other subjects are human inventions, created in an attempt to make sense of or explain what we do not fully understand.

We can apply this analogy to any technology or innovation we develop to solve problems and improve our lives. After all, the scientific method itself is built on the pillars of “observation,” “hypothesis,” and “experimentation.” Don’t get me wrong: this scientific method has been extremely beneficial and is how we’ve evolved to where we are today. However, there is a limit and risk to this methodology. From an observation, theories and hypotheses are developed that can be proven or disproven through experimentation. A scientific fact that we hold today could easily be overturned if a better explanation for a given observation is proposed. Even the advanced medicines and treatments we rely on today were discovered through observation—many of them, by chance.

Now, let’s venture into the realm of science fiction for a moment and ask ourselves: what would humanity be like if we were able to find answers to these fundamental questions? Where would we be if we could answer all the “whys”? With that brief reflection aside, let’s get into the main subject of this post. I hope I haven’t lost the reader’s interest.

One reason for our limited, almost blind, understanding of nature lies in the computational power available today, which, despite appearances, remains a major bottleneck in many scientific fields, preventing researchers from making critical breakthroughs. Even the most powerful supercomputer humanity has built—the Fugaku—is not fast enough to provide quick answers to common problems that need solving. As a result, the scientific community has organized its thinking, classifying problems in such a way that “optimization” of algorithms has become a key part of the puzzle. These classifications, in brief, include “P,” “NP,” “NP Complete,” and “NP Hard” problems. There are other subclasses, but my understanding is limited to these, and even that is superficial.

“P” represents a class of problems that can be solved by algorithms in a reasonable amount of time, with “P” standing for “Polynomial Time.” This means that we can find solutions to “P” problems in polynomial time, so as a problem becomes more complex, the time to solve it increases according to a polynomial function, rather than an exponential one. For example, multiplying numbers is a “P” problem, as there are computational algorithms that can solve multiplication in a timely manner. The larger the numbers, the more complex the problem becomes, and consequently, more computational power and time are needed to find the answer. However, this time increase follows a “straight line” on a time vs. number size graph. Other examples of “P” problems include:

• List sorting: arranging elements of a list in alphabetical or ascending order.
• Mazes: finding the way out of a maze from a starting point.
• Rubik’s Cube: solving the cube so that all sides are the same color.

We also have “NP” problems, where “NP” stands for “Non-Deterministic Polynomial Time.” These are problems where, given a correct solution, it’s possible to verify if that solution is correct using algorithms that run in a reasonable amount of time. However, it’s not possible to find the solution to an “NP” problem quickly. A common misconception is that “NP” stands for “non-polynomial,” but it actually stands for “non-deterministic polynomial problems.” Examples of “NP” problems include prime number finding, vehicle routing, and project/manufacturing scheduling.

An “NP” problem can become a “P” problem if a researcher develops an optimal algorithm that solves the problem quickly, in polynomial time. There is a hypothesis that eventually, all “NP” problems will become “P” problems, but we are not there yet—and it’s uncertain if we ever will be. This hypothesis raises the question: “Does being able to quickly test a solution also imply there’s a quick way to find the solution?” To date, no one has been able to prove this.

To better understand the difference between “P” and “NP,” let’s consider Sudoku. Today, the best computational algorithms developed to solve Sudoku still take a long time to calculate the correct answer, and the more complex the puzzle, the longer it takes to find the solution—following an exponential increase in time (not “P” time). However, given the solution to a Sudoku puzzle, we can verify its correctness with existing algorithms that run reasonably fast.

The “NP Complete” class consists of problems that are “NP” problems but have a special property: if one of these problems can be solved in polynomial time, all other “NP” problems can also be solved using the same or a modified algorithm. Examples of “NP” problems include Tetris, Naval Battle, Crossword puzzles, and the classic scientific problem of Protein Folding. If someone develops an algorithm that solves Sudoku in polynomial time, so that the problem is no longer categorized as “NP” and instead becomes “P,” this algorithm could help solve many other “NP” problems. This includes potentially finding a cure for diseases like cancer, as these cures rely on solving “NP” problems like Protein Folding.

Finally, we have the “NP Hard” class, which consists of problems that are at least as complex as the most difficult problems in “NP.” In computational complexity theory, “NP Hard” refers to problems that are informally known to be “at least as difficult as the hardest problems in ‘NP.’” More precisely, a problem is “NP Hard” when every problem in “NP” can be reduced to it in polynomial time. If a polynomial-time solution were found for any “NP Hard” problem, it would provide polynomial-time solutions for all problems in “NP.” It’s unlikely such an algorithm exists, as previously discussed. Furthermore, “P” problems, which can be solved in polynomial time, are a subset of “NP.”

The diagram below illustrates the relationships between “P,” “NP,” “NP Complete,” and “NP Hard” problems, assuming the answer to the question “Does being able to quickly test a solution also mean there’s a quick way to find the solution?” is either “no” or “yes.”