ADVERTISEMENT
Nautilus Members enjoy an ad-free experience. or Join now .
Sign up for the free Nautilus newsletter:
science and culture for people who love beautiful writing.
NL – Article speedbump

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.

Nautilus Members enjoy an ad-free experience. Log in or Join now .

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.

ADVERTISEMENT
Nautilus Members enjoy an ad-free experience. Log in or Join now .

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.

 

ADVERTISEMENT
Nautilus Members enjoy an ad-free experience. Log in or Join now .

close-icon Enjoy unlimited Nautilus articles, ad-free, for less than $5/month. Join now

! There is not an active subscription associated with that email address.

Join to continue reading.

You’ve read your 2 free articles this month. Access unlimited ad-free stories, including this one, by becoming a Nautilus member — 25% off for a limited time during our seasonal sale.

! There is not an active subscription associated with that email address.

This is your last free article.

Don’t limit your curiosity. Access unlimited ad-free stories like this one, and support independent journalism, by becoming a Nautilus member — 25% off for a limited time during our seasonal sale.