In this blog post, we will explain the P vs. NP problem, which defines the boundary between problems that computers can solve and those that are difficult to solve, in an easy-to-understand manner.
On May 24, 2000, the Clay Mathematics Institute in the United States selected seven unsolved problems in mathematics and offered a prize of one million dollars for each problem. These are known as the “Millennium Problems,” and anyone with even a passing interest in mathematics has likely heard of them. Given the high prize money, only the most challenging problems that had puzzled mathematicians for decades were selected. Even people who are not specialized in related fields may find it difficult to understand the problems. In this article, I will explain the P vs. NP problem, which is most closely related to computer science and is relatively easy to understand.
The P vs. NP problem is as follows.
“Are P problems and NP problems the same?”
Although it is a simple sentence, it is difficult to understand this question without knowing what P problems and NP problems are. A P problem is an abbreviation for a Polynomial-time problem, which refers to a problem that can be solved in polynomial time. For example, consider the problem of finding the nth term in the Fibonacci sequence. The Fibonacci sequence starts with 1 and 1, and each subsequent term is the sum of the two previous terms. Listing the first few terms, we get the following:
1, 1, 2, 3, 5, 8, 13, 21, 34, …
To calculate the third term of the Fibonacci sequence, you only need to calculate 1+1=2. To calculate the fourth term, you need to add twice: 1+1=2 and 1+2=3. Similarly, to calculate the fifth term, you add 1 + 1 = 2, 1 + 2 = 3, and 2 + 3 = 5, performing three additions. In general, to find the nth term of the Fibonacci sequence, you only need to perform n-2 additions. Therefore, the time required to solve this problem is n-2, which can be expressed as a linear polynomial in terms of n.
In technical terms, the “time complexity” of this problem is denoted as “O(n).” A linear polynomial is denoted as O(n), a quadratic polynomial as O(n^2), and so on. If the time required to solve a problem can be expressed as a polynomial, it is called a P problem. Examples of P problems are connected to many problems that can be solved by computers in the real world.
Simple operations such as addition and multiplication belong to P problems, and many software programs we use in our daily lives solve problems efficiently in this way. However, the situation becomes somewhat more complicated when we move on to NP problems.
On the other hand, NP stands for Non-deterministic Polynomial-time problem. Interpreted literally, it means “problems for which it is not known whether they can be solved in polynomial time,” but this does not accurately describe NP problems. The precise definition of NP is “a problem for which the time required to verify the answer is polynomial.” A representative example is the subset sum problem. The subset sum problem asks whether there is a subset of a given set of real numbers whose sum is zero. For example, consider the following set:
S = {-7, 3, 2, -5, 8}
There are a total of 31 non-empty subsets of S, and we need to find the subset whose elements sum to 0. How long would it take to verify that {-7, 3, 2, 8} is one of the solutions? All you need to do is add up all the elements of the set. In this case, you just need to calculate –7 + 3 + 2 + 8, which requires only 3 additions. The result is 6, so this subset cannot be the answer. Similarly, to check if {3, 2, -5} is the answer, you only need to perform 2 additions. Generally, when given a set with n elements, the number of elements in any subset is at most n, and the time required to verify whether the subset is correct is n-1. Thus, the subset sum problem has a time complexity of O(n) when verifying. Problems where verification takes polynomial time are called NP problems.
NP problems are often used to describe problems that are difficult to solve by computers in reality. Some of these problems play a very important role in modern society. For example, optimization problems and cryptography problems can be NP problems, and if they cannot be solved efficiently, enormous resources may be wasted.
Now, returning to the original question, what is the P vs. NP problem? Before we confirm this, there is one important point to note: NP problems and P problems are not mutually exclusive. Due to the name “NP,” it is easy to mistakenly believe that NP is not part of P. However, if we revisit the definitions of P and NP, we can see that all P problems are included in NP problems. Problems that take polynomial time to solve naturally also take polynomial time to verify. This can be expressed as P ⊂ NP. Therefore, confirming whether P=NP is ultimately the same as confirming whether NP⊂P. Thus, the P vs. NP problem can be written as follows.
“Does a problem that takes polynomial time to verify also take polynomial time to solve?”
If you have read the explanation so far, you may have one question. Why are we so obsessed with “polynomial”? The reason is that the time limit that computers can calculate “relatively quickly” is polynomial. Computers can calculate much faster than humans, but they also have their limits. Computers currently available on the market can perform 1 billion to 3 billion calculations per second. What would happen if the time required to solve a problem is 2^n? In the subset sum problem we looked at earlier, if we solve it by checking whether each subset is a solution, the number of subsets is 2^n, so we need to perform at least that many calculations. When n=20, it takes about 1 million calculations, which can be done in 1 second. However, if we try to solve this problem with n=100 using a computer, the calculation would never finish even if the Earth were to be destroyed. Even if the computer’s problem-solving speed were 1,000 times faster than it is now, the result would be the same. This is because the growth rate of an exponential function is incomparably faster than that of a polynomial. On the other hand, consider a P problem. A problem that takes n^3 time to solve requires 1 billion calculations when n = 1,000, so it can be solved in less than 1 second. Even if n increases by a factor of 10, the answer will be available in just 10 minutes. Since polynomial functions have a relatively slow growth rate, entrusting the problem to a computer will yield an answer in a relatively short amount of time. This is why numerous computer scientists have endeavored to find a way to solve NP problems within polynomial time. However, the P vs. NP problem remains unsolved and has plagued them for decades.
Among the concepts devised to solve this problem is NP-hard. Like P and NP, NP-hard is a type of problem. If a problem is NP-hard, then surprisingly, all NP problems can be solved in polynomial time! Among NP-hard problems, those that are NP are called NP-complete, and the subset sum problem we examined earlier is one of them. If a method for solving this problem in polynomial time can be found, it would prove that P=NP. However, no one has yet found such a method. Therefore, many people believe that the answer to the P vs. NP problem is “no.”
If the answer to the P vs. NP problem is P=NP, what would happen? There is a field that takes advantage of the fact that computers cannot calculate quickly, and that is cryptography. While computers can quickly calculate the product of two prime numbers, there is currently no known method to find the two prime numbers given their product within polynomial time. The widely used RSA encryption system leverages this fact, using the product of two prime numbers exceeding 100 digits to encrypt data, making it impossible to decrypt the original message without knowing the two prime numbers. However, since prime factorization is an NP problem, if P=NP, it would be possible to instantly decrypt RSA using a computer. This would completely undermine the entire encryption system. Of course, such an event is unlikely to occur easily, but considering the potential ripple effects, it is clear how important this problem is. If you’re aiming for a life-changing breakthrough, it might be worth giving it a try.
