In 2000, the Clay Mathematics Institute selected seven open problems and offered a $1 million reward to anyone who could provide a correct solution to one of them. Among these problems of paramount importance in science, known as the Millennium Problems, one stands out for its complexity, its apparent simplicity given the statement of the problem, and its potential impact if it were to be solved. Today I’d like to introduce you to the most iconic open problem in mathematics and computer science: the P vs. NP problem. How do we define what is effective and what is not? How do we solve a problem effectively? Does a problem that is simple to solve always have a solution that is simple to verify? What if the opposite were true? Are you ready to delve into the fascinating world of complexity theory through what is surely the most important mathematical problem of the millennium? Just a friendly reminder: don’t worry, this is a Level-0 post, so I’ll try to use as little math as possible, even though that will be a challenge here.
Let’s get rich!
1 ~ What is a problem?
In theoretical computer science, a problem is defined as anything that can be solved by what is called an algorithm, specified by an input and a desired output. An algorithm, a finite sequence of (mathematically rigorous) instructions, can be thought of as a recipe, where the ingredients are the inputs and the desired outcome of the recipe is the output. There are different types of problems: for example, we distinguish between those that are posed as yes/no questions (decision problems) and those in which we seek a valid solution for a given input (search problems). A simple example of a problem is finding the minimum in a list of numbers (the algorithm that solves this involves traversing the entire list and updating the minimum each time a new one is found). Another problem, a more difficult one this time, is solving a Sudoku puzzle. In fact, as long as there is a way to formulate a problem in a mathematically abstract way, we can then investigate whether there is an algorithm capable of solving it.
The work of a researcher in computational complexity theory1 is to “zoologize” these problems, that is, to classify them according to a criterion known as their complexity2.
1.1 ~ When you say complexity, do you mean how difficult the problem is?
Not really. What really interests researchers in this field isn’t how difficult a problem is to understand or solve (in the sense that the algorithm is lengthy or difficult to grasp), but rather how much resources (time and space) it uses.
But how do we measure the time it takes for an algorithm to run? You’ll agree with me that if you used a stopwatch to time an algorithm running on your laptop, the result would be very different from running the same algorithm on NASA’s supercomputers. Indeed, it seems pointless to measure an algorithm’s execution time in seconds. Instead, we prefer to count the number of basic instructions (or elementary operations) used during its execution. Let me explain with an example.
The algorithm described in Figure 1 compares each element with the candidate and updates the candidate whenever a new smaller object is found. Here there are 5 objects, and it took the algorithm 5 comparisons to find the result. This number of comparisons is our elementary operation in this algorithm. It allows us to measure the complexity of the algorithm independently of the machine (and the microprocessor’s speed in seconds). For 5 objects, 5 elementary operations; for 10 objects, 10 elementary operations; for 100 objects, 100 operations; for 1,000, 1,000… you get the idea. In this case, we say that the complexity is linear, because if we plot a curve showing the number of instructions as a function of the number of objects, we get a straight line.
Okay, now let’s imagine we’re using the algorithm shown in Figure 1 to sort these 5 objects from smallest to largest. All we have to do is find the smallest element, remove it from the list, and repeat the process until they’re all sorted. Thus, by repeating this algorithm of 5 instructions 5 times, we get a sorting algorithm. For 10 objects, we will have to repeat the minimum-search algorithm 10 times; for 100 objects, we will have to repeat it 100 times; for 1,000… in short, for objects, we will need to perform approximately elementary operations. For this reason, the complexity of this algorithm is said to be quadratic. Figure 2 illustrates just how noticeable the difference in complexity becomes as (the number of objects in our case) approaches infinity. A quadratic algorithm is therefore, in a sense, worse than a linear algorithm, regardless of the machine you use.
Top: linear complexity vs. quadratic complexity.
Bottom: quadratric complexity vs. exponential complexity.
Linear and quadratic algorithms are considered the most useful in practice, as they allow any computer to process a very large number of input elements without too much difficulty. Conversely, some algorithms have what is known as exponential complexity, meaning that the number of elementary operations grows exponentially with the number of input elements. These kinds of algorithms are terrible in practice because even a hundred input objects will give the world’s best computers a hard time3, and with each additional object, the complexity will only increase drastically.
Note also that measuring complexity is more complex in practice; notably, there are three ways to measure it: worst-case, average, and best-case. Another potentially interesting fact: it has been proven that the best sorting algorithm (as described above) cannot be linear4, and to date, the best sorting algorithms that use comparisons (as shown in Figure 1) are not quadratic, but linear-logarithmic (that is, of the form and thus more efficient than our naive quadratic comparison sort).
1.2 ~ So how do we categorize these problems?
Linear (), quadratic (), cubic (), in short, any algorithm whose complexity can be expressed as a polynomial ( raised to any power, for example ) is classified in what is called the P class. P stands for PTIME or polynomial: if there exists an algorithm of polynomial complexity for a given decision problem (see Section 1 for the definition), then that problem belongs to class P. If the best-known algorithm for a problem is exponential (e.g. ) therefore this problem does not belong to P. On the other hand, our algorithms for finding the smallest object and for sorting, described in Figure 1, are two algorithms that solve problems that belong to P.
1.3 ~ Oh, so NP stands for Non-Polynomial?
No! That’s what I sometimes hear from people who aren’t familiar with the subject. NP stands for non-deterministic polynomial (I agree, they could have chosen a better abbreviation). Don’t try to figure out why it’s called like that; just see how this class is subtly different from P. The NP class includes all problems that are verifiable in polynomial time. “Verifiable” is an important word here: a decision problem belongs to the NP class if its solution can be verified in polynomial time.
For example, imagine that you are solving the problem “Can the objects be sorted from smallest to largest” shown in Figure 1, that is, you are sorting the 5 objects using the algorithm described above. Then verifying the solution to this problem is the same as solving “Are the objects correctly sorted from smallest to largest?”, which is indeed a decision problem, and it can be solved in polynomial time (you simply need to examine each element from left to right, stopping when an object is smaller than the previous one): the sorting problem is therefore in NP. You’ll notice that sorting objects and verifying the solution are both problems solvable in polynomial time; therefore, sorting objects is a problem that belongs to both P and NP. In fact, the entire class P is contained within the class NP. Indeed, if it is “simple” to solve a problem, then it is “simple” to verify its solution. This is a long-known result: (P is contained in NP).
The $1 million Millennium Prize Problem, thus, seeks to determine whether this is a strict inclusion ( or which, mathematically, would imply that ) or whether NP is also included in P (which, mathematically, would imply that ). Figure 3 and Figure 4 visually illustrate the difference in the relationship between the classes depending on whether P NP or not.
To this day, certain problems are still considered to be in NP, and no polynomial-time algorithm has been found to move them into P (see Figure 3). This is the case, for example, with Sudoku: filling in a Sudoku grid is “hard”5, but verifying a solution, i.e. a filled-in grid, is very “easy” (it can be done in polynomial time, so it belongs to NP)!
2 ~ But then, how can we prove that ?
You only have two possible approaches: prove that P is different from NP, or prove that P is indeed equal to NP. For the first case, you must prove that there exists an NP problem (one that can be verified in polynomial time) that cannot be solved in polynomial time (and therefore does not belong to P). A single problem is enough to prove that P is strictly contained in NP (see Figure 3). In the second case, i.e. proving that P is indeed equal to NP, it’s more complicated. The most “straightforward” proof would be to show that all NP problems are also in P… and that’s a task that would take you forever, since you can always come up with new problems. No, the brute-force method won’t get us very far; we need to be smarter. Fortunately, experts in this field have found a trick to reduce the number of problems that need to be considered in a purported proof of : the NP-complete problems.
2.1 ~ NP-what?
There are NP problems that are so difficult that they become, in a sense, “universal”. Universal such that any other NP problem can be reduced to this kind of very difficult problem. These problems are called NP-complete problems6. You can think of them as problems that generalize all NP problems. I also like to think of them as the edges of the ellipses in Euler diagrams shown Figure 3. There’s nothing harder, nothing more “NP” than these NP-complete problems, and that’s why I like this analogy.
Because of this property, if you can solve an NP-complete problem in polynomial time, then that is equivalent to solving all NP problems in polynomial time. Using my analogy with Euler diagrams, you can think of this as mapping the edges of the NP ellipse to the edges of the P ellipse. And yes, if you’ve been following along so far, then you understand that to prove that , it is “enough” to solve (find a polynomial-time algorithm for) a single problem: an NP-complete problem. Today, we know of more than 3,000 of them. But many are constructed from, or can be reduced to, the most abstract NP-complete problem known: the 3-SAT problem.
2.2 ~ What is 3-SAT?
This time, the name was chosen more appropriately: the term SAT comes from “satisfiability”, and the number preceding it specifies the type of SAT problem based on the maximum number of variables (in this case, 3). All these words sound pretty complicated, so let me illustrate this problem with a little story (see Figure 5). Four astronauts, Alice, Bob, Charlie and David are preparing for a long-duration space mission. These four astronauts have items at their disposal that they may or may not take with them into space. NASA allows each of them to specify their own requirements (“I want to take this item with me”) and vetoes (“I don’t want this item to be taken on board”), but the total number (requirements vetoes) must not exceed 3, though they can specify fewer (hence the 3 in 3-SAT). The goal of the problem is as follows: NASA must guarantee each astronaut that at least one of their requests, a requirement or veto, will be satisfied (hence the SAT in 3-SAT). Determining whether such a satisfiability solution exists is a SAT problem.
At least one of their respective constraints must be met by NASA for everyone to be satisfied.
Since this problem is NP-complete, it is by definition NP, and therefore verifying a solution must be “simple”. Indeed, in the example shown in Figure 5, if NASA provides the list of objects selected for the trip, verifying whether it satisfies each astronaut’s constraints can be done in polynomial time. So the million-dollar question is: is this problem in P? Meaning, is it equally “easy” to solve? Or, in other words, is there a polynomial-time algorithm that solves this problem?
The answer does not seem to be the case, and to date, no one has been able to prove it.
3 ~ So should I forget about the idea of becoming a millionaire through math?
I have to be honest: yes. In any case, researchers aren’t trying to solve this problem to get rich. Not only does it hold immeasurable sentimental value for them, but solving it would also drastically change our view of mathematics and computer science, if not the world itself. In fact, the answer to doesn’t really “matter”; in reality, experts in the field are convinced that the answer is no (99% of the top experts in the field believe this7). On the other hand, proof that P is distinct from NP would inevitably yield revolutionary mathematical tools, or at least a breakthrough in complexity theory. If you still hold out hope that P = NP, imagine the consequences as well. If such a proof were to emerge and provide a way to find a polynomial-time algorithm for all NP problems, it would have an impact on the algorithms we use every day, particularly on the accuracy of our calculations (many hard NP algorithms today rely on approximation algorithms). It is impossible to predict what such proof might lead to: the consequences may remain theoretical, very limited, even if interesting to researchers, or they may have very practical applications, such as in the study of the genome, in cryptography (which protects our messages and banking transactions every day), in physics, and so on.
The sad truth is that we will probably never know. I’d like to quote my professor of Complexity Theory & Cryptography, who made a lasting impression on me when he said
4 ~ Can I ask a question?
I feel like the problem in Figure 5 is simple; I figured it out in just a few minutes. Why isn’t this problem included in P?
I illustrated SAT using a small example with only four participants. But it’s important to remember that in complexity theory, as discussed in Section 1.1, complexity isn’t measured by the time it takes to solve a problem, and certainly not based on such a small example. 3-SAT is an exponential problem, meaning that the best algorithm to date for solving it has exponential complexity depending on the number of participants () in my analogy in Figure 5. With , as in my example, the complexity isn’t noticeable in practice; it’s only when you start adding more and more participants that the complexity skyrockets (see the lower diagram in Figure 2 to better visualize this explosion in complexity as a function of input size).
What are the mathematical foundations needed to understand P vs. NP in more detail?
In a Level-1 post, I would introduce the reader to: deterministic and nondeterministic Turing machines to provide the true formal definition of complexity classes; Landau notation , which better describes complexity than words alone; and Boolean logic, including disjunctions and conjunctions, to formally describe SAT.
If we could prove that , would that have any implications for the other six Millennium Problems?
Yes. Stephen Cook, who introduced this problem at the Clay Institute in 1971, believed that such a proof would have both negative and positive consequences. The negative consequences would indeed affect the security of our current computer systems, which rely on cryptography based on complex problems (these problems would thus become easy to solve, and therefore no longer provide any security). The positive consequences, on the other hand, would concern mathematics: Cook already asserted in his 1971 seminal paper that if , then finding formal mathematical proofs (of reasonable size) in polynomial time would be possible, and this therefore applies to the other Millennium Problems. However, Grigori Perelman, a Russian mathematician, did not wait for to prove one of the seven problems in 2003 and also to decline the $1 million prize.
Are there other complexity classes?
Actually, there is an entire hierarchy of complexity classes. Just as with P and NP, the relationships between these other classes are still not known. Furthermore, complexity classes and hierarchies depend on the computational model used. For P and NP, the models are based on so-called deterministic machines: either an instruction in the algorithm is executed, or it is not. However, there are other computational models, such as probabilistic models. Such models are used, for example, to classify the complexity classes of quantum algorithms. Indeed, quantum computers perform calculations using probabilities; they are therefore not deterministic machines. Consequently, problems solved by such probabilistic machines are classified into classes such as BPP or, more accurately, BQP when referring to quantum machines. If you’re interested, one of the major problems in quantum complexity theory is BQP vs. QMA, which is the equivalent of the P vs. NP problem for quantum systems.
And if you’re now fascinated by complexity theory and the “zoologization” of problems, check out the Complexity Zoo, which lists the classes and hierarchies currently known to researchers.
