The Potentially Wonderful (and Slightly Scary) World of P = NP
The P NP problem is a puzzle that has baffled computer scientists for decades, and it remains a popular problem today both because of how simple it is to explain and how remarkable the outcomes would be if it were proven to be true. A casual definition of the problem is that if P and NP are equal then that means for every problem where a computer can quickly check a given answer a computer could also quickly find an answer. This may not seem very groundbreaking at first, but the repercussions would be massive if it is proven true, and some of the world’s greatest minds are currently working on it. Many computer scientists believe that it is simply impossible to prove that P equals NP, however it is also extremely difficult to prove that they are not equal. Either way, whoever is able to find the answer to this classic problem will certainly be remembered as one of the greatest computer scientists of their time, not to mention they would also receive a hefty million dollar prize offered to whoever first solves it.
On a recent Amtrak train ride from New York City to Boston, I read Lance Fortnow’s book The Golden Ticket: P, NP, and the Search for the Impossible. This is a nontechnical book targeted at people who just want to get an introduction to computational complexity without getting into the math behind it. If focuses mainly on the background and history of the P NP problem, a prediction on how the world would change if the problem was proven true, and some information on attempts to prove or disprove P equals NP. If you want to check it out for yourself, the book’s available on Amazon here.
In the first section of the book, Fortnow allowed us to enter a magical universe where we know every problem in NP is also in P, meaning any problem where a solution can quickly be verified can also quickly be solved. This would be big news for everybody, not just those in the computer science field. One of the first major impacts is the ability to make personalized pills that can cure cancer by inducing a specific type of protein folding, all made possible by specialized algorithms able to analyze DNA sequences in a patient’s blood. Other algorithms could be created that greatly improve our weather prediction abilities, allowing sports schedules to be made months in advance with little fear of having a game on a rainy day, not to mention computers capable of looking at statistics and choosing the winner of a game in the distant future with impressive accuracy. In addition to sports there are also huge ramifications to the art, music, and film industries. Computers are now able to analyze patterns in a Kubrick movie, a Bach symphony, or a Rembrandt painting and make new renditions of them all on their own. Entertainment could be boiled down to a series of algorithms because in a world where P equals NP, anything a computer can detect, it can create. While the impact on the medical and scientific fields is extremely positive, having robots that can create new art better than we can sounds fairly dystopian. Luckily, it is already extremely unlikely that P equals NP, and even more unlikely that we would be able to prove it if they were.
Fortnow also covered some of the historical attempts to prove or disprove P NP, and while the answer is still up in the air many hours have been spent trying to come to a solution either way. The current prospects for solving the problem soon look incredibly bleek. While there was a proposed proof to prove P does not equal NP in 2010, it was quickly debunked, and now there are no reliable leads for a method to go about the problem. This is not uncommon in the field of mathematics though, after all, Fermat’s Last Theorem was only proved in 1994 after being initially stated in 1637. So we may have a long time to wait.
There are some plus sides to living in a world where P does not equal NP (or at least one where we can’t prove it). One advantage is the safety of our information when transmitted over public networks. The current method that we use to secure our data is known as RSA, a form of public key encryption that relies on the assumption that factoring large numbers is hard. Essentially when sending information to a network, such as the wi-fi hotspot in your coffee shop, your computer generates a large number that is the product of two primes. It then uses this number to encrypt its messages, and it uses a private key for decrypting them. The reason this works is that a computer is not able to recover the private key from the public key, well at least not within a remotely reasonable amount of time. However, if P equaled NP then a computer would be able to easily break a very large number into its factors, breaking our current method of encryption. There are other ways of securing information, but none of them would be as easy to use as RSA. If P did equal NP we would most likely have to switch to a one-time pad system where information is encrypted using a random string of characters called a pad that can be used, you guessed it, one time. This could prove to be more difficult to implement because the pads would have to be generated by a trusted source, and you would need to have a new pad every time you wanted to send information securely. So should we all go out an start buying hard drives full of randomly generated one-time pads? Not yet, our information is mostly safe for now.
The P NP problem stands today as one of the largest unanswered questions in computer science and mathematics, it challenges the way we look at problems, and it could change the way we find solutions to them. It is an underlying element in the basis of the way we think, and it could have massive impacts on every aspect of our society. We most likely will not have computers writing our next blockbuster or predicting the World Series champion in April any time soon, but that doesn’t mean we can’t continue to imagine a world where it would be possible. Our technology is constantly developing and paving the way to look at many problems in different ways, we are gaining knowledge faster than ever before. If we keep looking forward we might eventually discover that we were living in this extraordinary world of P equals NP all along, or we might simply be chasing the impossible.