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 NP¹.

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 solutions². Cryptography is safe, and travelling salesmen will still have to travel the long way around³. 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.