Can the P vs. NP problem be solved, and how would the answer affect computer science and cryptosystems?

The P versus NP problem is one of the most challenging problems in mathematics and computer science, comparing the time it takes to solve a problem with the time it takes to check it. If solved, it could revolutionise many fields, including cryptography, but it remains unsolved.

 

On 24 May 2000, the Clay Mathematics Institute in the United States announced a prize of $1 million per problem for the solution of seven of the most unsolved problems in mathematics. These are known as the ‘Millennium Problems’, and most people with a moderate interest in mathematics have heard of them at least once. The high prize money meant that only difficult problems that have bothered many mathematicians for decades were selected. Even understanding the problems can be difficult for non-mathematicians without a degree in the field. In this article, we’ll explain the P vs. NP problem, which is the most relevant to computer science and the easiest to understand.
The P vs. NP problem is as follows
‘Are P problems and NP problems the same problem?’
It’s a simple sentence, but it’s hard to understand if you don’t know what a P-problem and an NP-problem are. P problems stand for Polynomial-time problems, which are problems that take polynomial time to solve. For example, consider the problem of finding the nth term of the Fibonacci sequence. The Fibonacci sequence starts with 1, 1, and the next term is the sum of the previous two terms. The first few terms are as follows
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 do two additions: 1+1=2 and 1+2=3. Similarly, for the fifth term, you can do three additions: 1+1=2, 1+2=3, 2+3=5. In general, it takes only n-2 additions to find the nth term of the Fibonacci sequence, which means that the time to solve this problem is n-2, so it can be represented as a first degree polynomial in n. This is the technical term for saying that the ‘time complexity’ of this problem is ‘O(n)’. We denote the first degree polynomial as O(n), the second degree polynomial as O(n^2), and so on. If the time to solve a problem like this is polynomial in the number of seconds, it is called a P-problem.
Examples of P-problems are associated with many real-world computer-solvable problems. Operations like simple addition and multiplication are P problems, and many of the software we use every day solves them efficiently in this way. But when we move on to NP problems, things get a bit more complicated.
NP stands for non-deterministic polynomial-time problem. It translates to ‘a problem that is undetermined whether it takes polynomial time or not’, but that doesn’t exactly describe an NP problem. The correct definition of NP is ‘a problem whose solution is polynomial in the time it takes to compute the answer given the problem. A typical example is the subset sum problem. Given a set of real numbers, the subset sum problem asks whether there is a subset whose sum is zero. For example, suppose you are given the following set.
S = {-7, 3, 2, -5, 8}
The number of (non-conjugate) subsets of S is 31, and we need to find the subset whose elements sum to zero. How long does it take to see if one of them, {-7, 3, 2, 8}, answers the question? Simply add up all the elements of this set. In this case, we can calculate -7+3+2+8, which requires only three additions. The value is 6, so this subset can’t be the answer. In the same way, to check if {3, 2, -5} is the answer, we only need to do two additions. In general, given a set with n elements, the number of elements in any subset is at most n, and the time to check if the subset is the answer is n-1. In other words, the subset sum problem has time complexity O(n). Problems that take polynomial time to solve are called NP problems.
NP problems are often used to describe real-world problems that are difficult to solve on a computer. Some of these problems play a very important role in modern society. For example, optimisation problems or cryptography problems can be NP problems, and not solving them efficiently can lead to a huge waste of resources.
Now, back to the original question: what is a P vs. NP problem? Before we get back to that, it’s important to note that NP problems and P problems are not mutually exclusive. Because of the name NP, it’s easy to mistakenly assume that NPs are not Ps. However, if you recall the definitions of P and NP, every P problem is an NP problem. A problem that takes polynomial time to solve will naturally take polynomial time to check. We can denote this as P⊂NP. Then, checking whether P=NP is equivalent to checking whether NP⊂P. So, the P vs. NP problem can be written as follows
‘If a problem takes polynomial time to compute, does it also take polynomial time to solve?’
If you’ve read this far, you might be wondering: why are we so obsessed with ‘polynomial’? The reason is that polynomial is the time limit that computers can compute ‘relatively quickly’. Computers can calculate much faster than humans, but they have their limits. Computers on the market today can typically perform between one billion and three billion operations per second. What happens if the time to solve is 2^n? For the subset sum problem we looked at above, if we solve it by checking the answer for all subsets, we have 2^n subsets, so we need to do at least that many operations. For n=20, we only need to do about 1 million calculations, so we can solve it in less than a second. However, if you try to solve this problem on a computer with n=100, it will take you until the end of the world. This is true even if the computer solves the problem 1000 times faster than it does now. This is because the growth rate of exponential functions is incomparably faster than that of polynomials. On the other hand, consider the P problem. A problem that takes n^3 to solve can be solved in 1 second if n=1000 because it requires 1 billion operations. Even if n is 10 times larger, you’ll only need to wait 10 minutes. Polynomial functions grow relatively slowly, so if you leave it to a computer, it can be solved in a relatively short time.
For this reason, many computer scientists have tried to find ways to solve NP problems in polynomial time. However, the P versus NP problem has remained unsolved and has plagued them for decades. One of the concepts designed to solve this problem is called NP-hard. NP-hard is some kind of problem, like P or NP, that if you can solve it in polynomial time, then surprisingly, you can solve any NP problem in polynomial time! NP-hard problems that are NP-complete are called NP-complete, and the subset sum problem we saw above is one of them. If we could find a way to solve this problem in polynomial time, we could prove that P=NP. However, no one has found such a method yet. That’s why many people think that the answer to the P vs. NP problem is no.
What if the answer to the P vs. NP problem is P=NP? There is one field that takes advantage of the inability of computers to compute quickly: cryptography. While computers can compute the product of any two primes quickly, there is no known way to compute the product of two primes in polynomial time given the product of two primes. The world’s most popular RSA cipher takes advantage of this fact by encrypting a message using the product of two prime numbers with more than 100 digits and making it impossible to decipher the original message without knowing the two prime numbers. But prime factorisation is an NP problem, so if P=NP, a computer can crack RSA in a fraction of a second. The entire cryptosystem would be completely broken.
Of course, that’s not going to happen easily, but think about the ripple effect and you’ll see how important it is. If you’re looking to win the jackpot of life, it’s worth a shot.