P=NP? P!=NP? What The Hell Is That All About?

Firstly, an apology.  This is an attempt to explain, to the layman, something which I barely understand myself.  This might not work....apologies all round if it doesn't...

You may have heard that somebody recently submitted a proposed proof to the P=NP problem in maths.  The someone in question is  Vinay Deolalikar, a researcher at Hewlett Packard.  Whilst he developed the paper outside of company time he's still speaking within his field of expertise, this isn't just an obscure pure maths problem, it's one that has some very important consequences for virtually anyone who uses a computer these days.  That's you by the way, unless you're reading this on a printout, and kudos if you are.

The P=NP problem is, in plain English, about how long it takes to find the right answer when there's lots of answers.  It's all about a particular kind of problem, one that produces a lot of potential answers - the Travelling Salesman problem is a classic example.  Imagine you have to visit five different cities, you know the distances between each of them, and you want to visit every one of them, from any starting point, and travel the shortest distance possible.  

The obvious solution is to check every possible trip and find the shortest that way.  The number of possible trips is the number of cities (5) times the number of the next city you could visit, times the next....and so on.  "Five factorial" if you want the proper name for it, or "5!" in shorthand.  (This, annoyingly, has nothing to do with the "P!=NP" you may have seen, even though there's an exclamation mark involved.  There's only so many keys on a keyboard so while mathematicians use "!" to mean "factorial" programmers and computer scientists use "!=" to mean "does not equal", we'll come on to that bit later)

So we've got 120 different possible trips...just find the shortest of them, easy, you can probably do that without using your fingers, let alone a computer.

So what about six cities?  Turns out there are 720 trips to test.  OK, it's do-able in your head, but a computer might be helpful.

Seven cities: 5040 trips.

Eight: 40,320

Nine: 362,880

To find the shortest distance between fourteen cities you need to test 87,178,291,200 trips, which is getting a bit silly.  In fact, you very quickly get into the realms of needing a supercomputer, and beyond than even faster.  It's an "NP Complete" problem, and computers hate them.

The big question is, can you find the shortest route another way?  Plenty of people have tried...a particularly cool method is called "ant colony optimization", you write a computer program that simulates ants.  Yes, really, ants.  Each one wanders around between the cities (OK, ant hills) leaving a trail of scent behind it which slowly evaporates.  Whenever an ant reaches an ant hill it follows the path with the strongest scent.  Very quickly you end up with a strong scent trail on what is usually the shortest route.

And therein lies the rub.  Usually.  That doesn't count in maths.  However cool your insect based algorithm is, even if it works 99.999% of the time, it's not a proof.  You can never be sure it's the shortest route without testing it against every possible route, which brings us back to square one and the "computers hate NP Complete problems" thing.

What the P=NP problem really is is the simple question "Is it even possible to find a quicker solution than testing every trip?"

Actually, it's slightly more technical - it asks "If solutions can be checked quickly, can a particular solution be found quickly?".

In the case of the Travelling Salesman this makes a little less sense, but a better example is prime numbers.  Prime numbers can be checked to see if they're really prime quite quickly.  Take 6,538,732,799,420,108,322 for example.  That's a big number, but is it prime?  The answer, fairly obviously, is no.  It ends in a 2, so it's not prime.  That's an example of a really easy check that takes no time at all, we don't have to try dividing it by every possible number because there's a more obvious solution.

Now try finding the next prime number after 6,538,732,799,420,108,322 (without looking it up on the internet...)

Bit trickier huh?

That's a good example of the P=NP problem right there...is there, even in theory, a quicker solution than testing every number bigger than 6,538,732,799,420,108,322 until you find a prime one?  (And trust me, that'll take ages).

Pic courtesy of the wonderful xkcd, by kind permission.

The majority of mathematicians and computer scientists believe, in fact, that P!=NP, that there are some problems you just have to do the long way.  The longest possible way in fact.  And the suggested proof supports this.  If Vinay Deolalikar is correct then several things will happen:

1. He'll win $1,000,000 for cracking one of the Millennium Problems, one of the great mathematical problems of the last few hundred years.  (Another fell in March this year with Grigori Perelman's proof of the Poincare Conjecture)
2. He'll quite possibly win a Fields Medal, the maths equivalent of a Nobel Prize....but only if he's under 40 years old.  
3. The world of cryptography will heave a sigh of relief.
4. There's every likelyhood that the share prices of the major banking electronics companies will peak a little.

Cryptography and banking are the "real world" news here in many ways.  Whenever your bank details or credit card details are sent over the internet there's an NP Complete problem involved.  Your card details are jumbled up using very big prime numbers, and un-jumbling them is very, very nearly an NP Complete problem.  There is a shortcut, but it 100% relies on one little piece of information about how the jumbling was done.


To hack the transmission you either need a copy of the bank's bit of information (a stunningly well guarded and regularly changed bit of information too), or you need to spend several years or even decades with the most expensive computer on the planet running at full whack.  You can do it, but by the time you do the card will have expired.


You can crack bank codes, but it's not worth it.  The question has always hovered though...could some bedroom genius suddenly turn up out of the blue with a quick way to crack it?  If s/he did then secure internet banking as we know it would cease to exist...a replacement would probably be found quite quickly, but the same fear would exist, could the replacement also be cracked at any time?


If P!=NP as suggested then it means there will never be a quick way to break the banks codes.  As computers get faster the banks can simply use bigger and bigger prime numbers, of which there's an infinite number.


Until quantum computers come along at least, but that's a whole other story....