Tuesday, August 10, 2010

P!=NP (maybe)

Serious geekery ahead: It seems there's a new, credible proof published showing that P is not equal to NP. Of course, if you understood that, then you've probably already heard about it by now.

It's perhaps the most fundamental and most famous unsolved issue in computer science, and one of the top unsolved mathematical problems. For a really good writeup (much better than mine), check out Good Math, Bad Math. Me, I love working on brain modeling and behavior, but at times like this I kind of wish I'd stayed with Computer Science.

Complexity theory deals with how difficult problems are to solve in principle. It divides problems up into classes, depending on how hard they are to solve. P (for "polynomial") are problems that have an efficient solution: sorting a list, for instance, or finding the shortest path between two points. Since there are efficient methods - algorithms - to solve them it means we can sort huge lists, and your car navigator can find the best route even for very long trips.

NP is a class of problems that doesn't seem to have any efficient way to solve them. The best way is more or less to just try all possible solutions one after another and see which one fits. Lots of important problems, like encryption, are in NP1.

A famous example is the Traveling Salesman problem: you get a list of cities, and you need to find the shortest path that connects all the cities and returns you to the starting point. It turns out that the only way is to try every possible route, and pick the shortest one (there are ways to trim the list of routes but it doesn't really help). For small number of cities it's easy. But as the number grows it quickly becomes impossible; the number of combinations quickly grow too large (it's called "combinatorial explosion").

Here's the thing, though: nobody has proved that those NP problems really lack efficient solutions. It's always been possible that there's some clever way of solving an NP problem efficiently. And because of a quirk in how some of those problems are structured, if you could solve one of them - any one - then they all become solvable. That includes breaking most types of encryption.

Now this group at HP seems to have a credible proof (pretty much unreadable unless you're doing computer science for a living) that P and NP really, truly are different. NP problems don't have efficient solutions2. Cryptography is safe, and travelling salesmen will still have to travel the long way around3. If, that is, the proof holds up. It is over 100 pages long, and long proofs are often found to contain errors. It could be correct; it could have errors that turn out to be fixable over time; or it could have serious errors that doom this proof. But even if this proof fails it's likely to pave the way for new better attempts in the future.

#1 I'm glossing things over a bit; NP actually includes P, so when we talk about a problem "being in NP", what we mean is really a problem that's in NP but not in P. The question of whether P = NP is thus really if there are any problems in NP that are not also in P.

#2 How important is this? It is hugely important, but it is verification of something most people already assumed to be true. It would have been much more surprising to get the opposite result.

On the other hand, even if a problem is NP we can still often solve it quickly in practice. For the travelling salesman, for instance, it's extremely hard to find the single best path. But if you're content with just finding a good path, but not necessarily the single best one, then it becomes easy. Other problems in NP may be almost impossible for some rare specific inputs, but easy for almost all cases you're likely to actually want to solve.

#3 A problem like this may seem pointless. Who cares what the optimal city tour is? Computer science often use toy problems like this because they're stripped of any unneeded complexity, memorable and easy to reason about. And real-world problems are often equivalent to a toy problem; if you can solve a toy problem you can solve a lot of real, important problem the exact same way. So it's really not as frivolous as it may seem.


Jonas said...

Really cool stuff. I didn't discover it until today - taking holiday, also from Google Reader. I don't even dare to look at the manuscript, but it is pretty cool to look at all the buzz that has been going on around the Internets.

For example, did you see Scott Aaronson's offer to top up the Clay prize with 200K$ of his own money, just to tell all the people buggering him for comments how serious he was when believing that the proof will turn out to be incorrect? That blog post turned into a monster of a comment thread and a follow-up post, mostly about Scott's possible motivations for making such a bet, as well as the ethics involved in that kind of scientific betting.

Whenever I have more time, I have to read through those threads - it's better than a movie!

Janne Morén said...


It's pretty exciting, though I don't even pretend to understand the proof myself. And as far as the proof being flawed I think it's a fair bet to say it is. I don't know of any large proof like this that doesn't turn out to hold several flaws, some of them serious.

The question isn't if it's flawed; the question is rather if the inevitable flaws are fixable or if the proof is dead in the water.

Jonas said...

As far as I gathered, the proof itself did not really stand against the last few days' massive analysis, but it is taking an interesting new approach that might maybe possibly lead to something. Or something like that. I really should read some more...