Why You Care if P=NP

I had started a long thought on one of the toughest open problems in computing and realized I had stepped in too many scientific puddles along the way. So here is a long thought in two parts; the first is for everyone (including non-math, non-computer science people) because I believe this is the kind of problem that equally fun and important to consider. The issue concerns the extent and limits of what we can (and possibly cannot) do with computers.

Computer scientists call this “The P=NP Problem”. I started thinking about it again recently, after a 27-year hiatus, due to a “plate o’ shrimp” set of events: A huge buzz in the computing community around a proposed solution to the problem, thinking about my former CS-conspirator Tom (who actually got this stuff) and the publication of my former thesis advisor’s book on the problem. Thesis advisors retain an avuncular relationship with their students for decades, whether or not the advisors know it — and in the last year when the Princeton community lost a number of professors who had advised the classes of the mid-80s, I saw an enormous outpouring of emotion from my friends. Seeing Dick Lipton’s name in the press again was equally exciting and challenging, triggering some of those feelings, making me shell out nearly a Benjamin for his book. I started reading two days ago, thinking that I’d do an amazon.com review, but got thinking about hard CS again and here we are.

What is the P=NP problem? It’s been unsolved for the better part of fifty years. It involves a famous mathematician (Kurt Godel, attracted to Princeton by Einstein) and the father of the modern computer (John von Neumann) exchanging notes about things so complex and divisive that any news about a potential solution immediately accretes a small conference to explore the idea. If you can solve it, you win a cool million dollars as P=NP is one of the Millenium Problems.

Basically, there are two types of problems that we look at in computer science. Some are easy to solve, and we know that we can solve them in a predictable and bounded time. If you have 1,000 numbers to sort, and your computer can sort them in 1 second, then sorting 10,000 numbers will take 10 seconds or so (Acutally less, but I won’t get into the math here). These are known as “P” class problems.

There are other problems that have answers that are easy to verify, but the answer can’t be calculated in any predictable or bounded way. Here’s a goofy example: you take your really big truck to Costco for a major snack food run. Unfortunately, you went when you were really hungry and the Giants were playing a late game, so you overloaded just a bit. Each box of candy, each pallet of soda, and each 100-count frozen burrito box has a particular weight as well as a specific, non-crushable height, length and width. You know the volume of your truck and its weight capacity, and you know the maximum interior height, length and width of the cargo space. What’s the best way to pack the truck without crushing anything, knowing you have to get chips, burritos, drinks, candy and at least one healthy alternative? You know that some of those boxes aren’t going to fit, so you have to make trade-offs. You need to worry about the total width, total length and total height of the stacked boxes, the total volume of everything inside, and the total weight of what you load on those rear wheels. It’s easy to tell if your trial packing meets the criterion – the rear door closes without any crunching sounds, and you can check off the list your friends (and spouse) gave you. Checking the solution is easy. Finding it is impossible. Which gives you a perfectly good reason to swear at your mountain of boxes in the Costco parking lot.

The reason the truck packing problem is impossible to solve (even though we can check answers very simply) is that calculating an answer boils down to determining every possible combination of box packing and stacking, and then checking each one. There’s no easy, well-sequenced way to solve this one. If you have only five boxes, there are more than 100 ways to pack them. With a thousand boxes and a photographic memory that helps you verify the shopping list in a second, you’re going to spend years finding a solution (however, the Swedish Fish will not have passed their expiration date, although the burritos will be ancient history). These are known as “NP” problems, and despite the goofy example, they exist in the real world.

What’s the point of P=NP? It asks whether the two classes of problems are the same, or fundamentally different. If they are the same, it means that NP problems have deterministic, bounded solutions that we simply haven’t discovered yet. If they’re different, then there are NP problems for which no such solution exists. There is a good news/bad news conundrum wrapped around the question of P=NP as well, because the answer challenges our existing approaches to, and applications of, computing.

Here are two problems that fit the NP category: when you are using a “secure” internet site, your network traffic is encrypted using some very large numbers to generate the encryption. Deriving the large numbers underlying the secret channel is a problem in NP, and you’re basically pretty happy that it belongs in that class. Since brute-force guess-and-test attacks will take years (as in millions of years) to solve the problem, it’s effectively impossible for an attacker to reverse-engineer the security mechanisms and tap into your personal or financial information. Having problems in the NP space is quite helpful when you want to ensure your computation only goes in one direction (hence the nickname “trapdoor algorithm” for this type of computation).

On the surface then, having P and NP be different is a good thing, and we should be cheering on the theoreticians trying to prove that result. But here’s a different NP problem: Given a long string of proteins, like a virus or genetic marker, find another string of proteins that will fold neatly into it, as a vaccine or treatment. Protein folding is way out there in the complexity spectrum. If P and NP are different, then we lose the ability to fully automate, with a higher degree of certainty and precision, some of the pressing issues in biochemistry and computational chemistry.

It may be another year, or ten years, or hundred years before we develop the computing tools and disciplines to prove the P=NP question either way. Fermat’s Last Theorem stood unsolved for almost 360 years until a bit of computer science work shed light on a novel approach. Insights needed to tackle P=NP may come from other disciplines, and that’s the benefit of computing permeating so many aspects of our social domains.