If you think computers have gotten really good at solving problems—like voice recognition, or self-driving cars—then your mind would be blown by what they could do if P = NP.
Internet cryptography would come crashing down. Voice and image recognition would become near-perfect. Mathematical proofs would be greatly simplified. The stock market would dramatically change.
All by proving this one theorem, which states that finding the solution to a problem would about as hard as checking it. Think about that: In your high school algebra class, was it easier to plug the answer that your teacher gave you into the equations to see that it worked, or to come up with the answer? If P = NP, those two tasks would about as hard as each other.
Or, to use a more important example, what if you had to factor a large number into primes? Once you have the prime factors, it’s easy to check if they multiply together to give the original number, but finding the factors requires, in general, a slow, laborious process. The difference in speed between finding prime factors, and checking prime factors, is at the root of most internet security. If there were no difference, there would be no security.
That’s a big if, however. So big that the Clay Mathematics Institute will give you a million dollars if you prove whether or not P = NP. Some consider it one of the most important problems in all of theoretical computer science.
One of those people is Scott Aaronson, theoretical computer scientist, professor at the Massachusetts Institute of Technology, author of the popular blog “Shtetl-Optimized,” and the book Quantum Computing Since Democritus. We asked him, what would happen if we actually proved P = NP? You can see the full interview here.
