The P-NP problem is one of the most challenging problems in mathematics, asking whether there is a fast way to find the correct answer to a given problem. If solved, it could revolutionize the way we solve optimization problems in industries as diverse as aircraft scheduling and semiconductor design.
A thief enters a jewelry store, looks around, and for a brief moment ponders. “I would love to take all the jewelry, but unfortunately, there is a limit to how much weight my bag can hold. What gems should I fill the bag with to get the most money?” There are too many possible combinations of gems in the bag to calculate their value. If it’s too time-consuming to calculate by hand, you can think about using the most advanced computers and software with the best algorithms. Unfortunately, no algorithm currently exists to solve this problem quickly. Even with the most powerful computers, it would take thousands of years or more. The reason this problem, called the “knapsack problem,” is so difficult is that it is similar to the P-NP problem, a math challenge that only 53% of mathematicians believe will be solved before 2100.
The P-NP problem is one of the world’s top seven math challenges. The Clay Mathematics Institute in the U.S. has listed seven unsolved math problems for the 21st century and offered a $1 million bounty for each one. Only the Poincaré Conjecture has been proven, but the other six, including the P-NP problem, remain unsolved and challenged by many mathematicians. Many optimization problems in various fields of society, including the thief’s example, are “hard problems” with high computational complexity. The P-NP problem is to prove whether there is an easy way to solve these “hard problems”.
What is Computational Complexity?
Computational complexity is an objective measure of how difficult the problem we are trying to solve is. In this context, hardness doesn’t mean that there is no solution to the problem, but rather that there is no algorithm that can solve the problem quickly.
Here’s an easy example. There are 100 balls with different random numbers written on them.
– Problem 1: What is the maximum value of the numbers written on the balls?
– Problem 2: Is there a set of balls such that the sum of the numbers written on the balls is 100?
For Problem 1, if you take out one ball and replace it when it has a larger number than the one you are holding, the number you end up with is the maximum, which means you need to make 99 comparisons in total. By comparison, for Problem 2, we need to check if there is a set that sums to 100 for every combination that can be made with 100 balls, which means that in the worst case, we need to do about 2 to the 100th power (* the total number of subsets) of computations. Even assuming a supercomputer performs a quadrillion operations per second, this would take an unimaginably long time, about 23 quadrillion years.
An algorithm is called a polynomial time algorithm if, as the number of balls (N) increases, the number of operations (N-1) does not exceed a polynomial function of the number of balls, as in the solution to Problem 1. The existence of such an algorithm can be the difference between an easy problem and a hard problem.
P=NP?
Notice that finding the answer to the hard problem 2, for which no polynomial time algorithm exists, requires a huge amount of computation, but verifying that the answer is correct is very simple. Given a set of balls, it should take less than 10 seconds to verify that the sum of the numbers written down is 100. In other words, just because a problem is easy to compute doesn’t mean there is an easy way to solve it. Whether there is an easy way to solve it and mathematicians haven’t found it yet, or whether there is no easy way to solve it in the first place, remains to be seen. This is the P-NP problem.
The P set is the set of easy problems that can be answered in polynomial time, such as Problem 1, and the NP set is the set of problems that can be checked for correctness in polynomial time. A P-NP problem is the problem of proving whether the P-set and the NP-set are equivalent sets. It is self-evident that the P-set belongs to the NP-set. However, it has not yet been proved that every problem in the NP set is in the P set. If this is proven, it means that every problem that is easy to compute has an easy-to-complete solution, i.e., we would no longer need 10^28 years to solve Problem 2.
NP problems and real life
It’s not just the mathematical difficulty of the P-NP problem that makes it one of the top seven math problems of all time. The reason it is so important to prove is that it is closely related to solving real-world problems. Real-world problems in industries as diverse as airplane scheduling, semiconductor design, drill machine placement, genomic data analysis, astronomical telescope placement, and X-ray crystallography are NP-hard problems that take a long time to solve. However, we have yet to discover an algorithm for making optimal decisions quickly, and we don’t even know if such an algorithm exists. So, in the absence of a polynomial-time algorithm, how do we currently make decisions about real-world problems?
Scholars in various fields such as mathematics, computer science, industrial engineering, etc. are researching and developing various approximate solutions that approximate the optimal solution to solve real-world problems. Consider the thief’s problem again: if finding the optimal combination of gems would take a long time, the alternative is to find a way to make decisions quickly and efficiently with a relatively small profit. One option might be to calculate the value per weight of each gemstone and fill your bag with the gems with the highest value per weight first. This is an approximate solution called the greedy heuristic, which has been put to practical use when decisions need to be made quickly. Although these approximations are not optimal, they are very helpful in making decisions in real-world problems with time constraints. Furthermore, some approximate solutions are becoming more sophisticated, with some approximations being able to approximate the optimal value for a given problem to within 0.5% error.
The security industry and NP problems
In contrast to the above industries, there is one industry that does not want an easy algorithm to be found to solve NP problems. This is the security industry. Current security schemes are organized in a way that uses the NP problem in reverse. If you know a password, it’s easy to verify that it’s the right password, but it’s not easy to find it because there is no polynomial-time algorithm for finding it. Perhaps the entire security industry is hoping that the P-NP problem will remain a perennial conundrum.
However, proving P=NP does not mean that all NP problems are easily solvable. However, it is clear that the existence of a polynomial-time algorithm will spur many researchers to study polynomial-time algorithms for hard NP problems. This will have a significant impact on efficiency improvements and optimization of real-world problems. Conversely, if it turns out that P≠NP, it means that there is no such method, which means that many NP problems will remain intractable in the real world. Either way, it will be interesting to see what the outcome of this conundrum will be.
