A diagram showing the relevant complexity classes in the P vs NP problem. “P” problems are solvable in polynomial time; “NP” problems might be solvable in polynomial time, and are checkable in polynomial time. “NP-complete” problems are NP problems such that finding a solution to them would let you solve every NP problem. “NP hard” problems are problems at least as complex as the NP-complete problems. Phew.Graphic: Behnam Esfahbod (Wikimedia Commons)
You may have heard of the famous P versus NP problem. If you can prove or disprove its cryptically short equation, you’d be a million dollars richer—and maybe even billions of dollars richer, depending on your scruples.
The importance of P versus NP is mainly in its consequences for computing. It happens to be one of the seven Millennium Prize Problems, meaning The Clay Mathematics Institute of Cambridge, Massachusetts will award $1 million to whomever manages to prove or disprove the statement. But should you prove that P in fact does equal NP, you wouldn’t even need the $1 million prize. As theoretical computer scientist Scott Aaronson explained last week at a lecture in a stuffy auditorium at Los Alamos National Lab in New Mexico, proving that P=NP would open up some intriguing possibilities.
“If someone proves P=NP, the first thing they should do is steal $200 billion in bitcoin. The second thing they should do is solve all of the other Millennium Prize Problems,” Aaronson said.
To understand this, you need to know that computers are devices that solve problems, abstracted into code readable by the physical computing device, based on the principles put forth by Alan Turing. Solving problems takes a number of steps and a certain amount of time, with the amount of time required increasing as the problem grows larger.
“P” refers to the problems that computers solve all the time, from something as simple as multiplying two numbers to more complex tasks like browsing the internet. As a problem grows in complexity, the amount of time it takes to solve it grows in “polynomial time,” where a polynomial is a number with a power and a coefficient (like n2). If a problem is solvable in n2 time and you double the size of the input, then the amount of time it would take to solve would go up by four.
Yet there are plenty of problems where one can determine that a given answer is correct in polynomial time, but actually getting to that answer may or may not be possible in polynomial time. These are called “Nondeterministic Polynomial time” or NP problems. Sudoku is an NP problem—hard to solve, easy to check. Another important example today is factoring large numbers into prime numbers. For now at least, it takes a very long time—slower than polynomial time—to factor very large numbers into primes, but checking that an answer is correct is as simple as multiplying the resulting numbers together. Indeed, this exact idea is the basis of modern encryption, which relies on generating security keys that are easy to verify but hard to crack.
Newer mathematical proofs have found, and might continue to find, P solutions to some of these NP problems. The P versus NP problem asks whether every NP problem has a P solution, or if there exists some NP problem that can absolutely not be solved in P. It seems like it should be obvious that P does not equal NP, but it is not rigorously mathematically proven. And if you happen to prove that P does equal NP, you will have also demonstrated that there are polynomial-time algorithms for a whole lot of very important computer problems. You could make yourself very rich—bitcoin mining and security keys rely on hard-to-solve, easy-to-check NP problems.
Quantum computers, which are based on different mathematics than classical computers, do not promise P solutions to every NP problem. It was once thought that they might be able to solve the hardest class of NP problems, called NP-complete problems. If you could find an efficient solution to those, you’d be able to find efficient solutions to all NP problems. This includes the traveling salesman problem and a host of other similar optimization problems. But quantum computers haven’t lived up to this hype. Instead, quantum computers might solve some P problems in a shorter time (as in, with a lower polynomial) or move some NP problems into the quantum generalization of P, called BQP or “Bounded-Error Quantum Polynomial Time.”
So go out there and try and prove that P does, or does not, equal NP. If you’re successful, you’ll make at least a million dollars, and perhaps much, much more. If you’re unsuccessful, well, hopefully you will have led a meaningful life researching computational theory.