P vs. NP is a problem in theoretical computer science and mathematics that was developed by two computer scientists, Stephen Cook and Leonid Levin, in 1971 and 1973 (1). The problem they dealt with was classifying different problems. Cook and Levin established two types of problems: P problems and NP problems. P problems are problems that can be solved quickly (in polynomial functions of time) while NP problems are problems that cannot be solved quickly (only expressed in exponential functions of time).
One of the first NP problems to become commonly known (especially by mathematicians) is the traveling salesman problem (TSP). Erica Klarreich, at Wired, describes the TSP: “Given a collection of cities connected by highways, what is the shortest route that visits every city and returns to the starting place?” (2). One of the difficulties with NP problems like this is that in order to solve them you have to try all combinations to prove your answer is right (3). Another NP problem forms the basis of modern encryption and public-key cryptography. The very difficult problem of factoring large numbers that are the product of two prime numbers (prime factorization) is an NP problem that prevents attackers from gaining access to your computer unless they have enormous resources and time. However, what if prime factorization problems could be solved easily as P problems?
Over time, some NP problems have turned out to be solvable as P problems (for instance, solving Rubik's cubes) by writing better algorithms or developing mathematical solutions. This led computer scientists and mathematicians to pose the question, “Are all NP problems just P problems that we haven’t been able to find quick solutions for (in polynomial functions of time)?” Right now, most computer scientists think that P does not equal NP. An opinion poll by William Gasarch, professor of computer science at the University of Maryland, College Park, found that 61% of researchers didn’t believe that P = NP, 9% believed P = NP, and 30% didn’t know if the problem was solvable (4).
What if P were equal to NP?
All NP problems would be solvable (except NP-hard problems). Problems that deal with efficiency (finding the most efficient answer) would be solvable. Thus, all shipping companies could find the optimal path to reach customers. Work schedules with thousands of employees could be optimized for maximum performance. Modern encryption, including cryptocurrency, would be easily hackable. Lance Fortnow, a computer scientist and complexity researcher, explains that if P were equal to NP, it would have an immense impact on mathematics, “One could find short, fully logical proofs for theorems whose proofs are usually extremely long. We can then find proofs of theorems that have reasonable length proofs say in under 100 pages” (5).
Even though this problem will most likely not be solved in this century, it poses interesting questions and reveals how much we still need to learn in mathematics and computer science.
References:
1) “P Vs NP Problem.” Clay Mathematics Institute, www.claymath.org/millennium-problems/p-vs-np-problem.
2) Klarreich, Erica. “Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem.” Wired, Conde Nast, 14 Aug. 2018, www.wired.com/2013/01/traveling-salesman-problem/.
3) Daniel Miessler. “P Vs. NP Explained.” Daniel Miessler, danielmiessler.com/study/pvsnp/.
4) Rosenberger, Jack (May 2012). "P vs. NP poll results". Communications of the ACM.
5) Fortnow, Lance. “The Status of the P Versus NP Problem.” ACM, 1 Sept. 2009, cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext.