P vs NP in layman’s terms using the Travelling Salesman Problem

The Travelling Salesman Problem

Tom’s problem

Meet Tom Smith and his sales territory. We begin by talking about Tom Smith’s Problem (let’s call it TSP). At the start of each sales year Tom purchases tickets to every single city in his territory. In order to avoid wasting time on pointless stop overs Tom wants to visits each city only once. This maximises time spent in the field selling and minimises cost. He also plans his trip such that his final stop takes him back home to Smithville.

In mathematics this is called a Hamiltonian Cycle: A path which (a) visits each point on a graph only once, (b) visits every single point on the graph and (c) forms a loop

Is there a cheaper path?

Right now the trip costs $400 in total. One day Tom notice’s a peculiarity: the cost for flying between cities has nothing to do with how far apart they are. He realises that “if I plan my trip just right, maybe I can find a set of flights cheaper than $400!”

He begins by randomly choosing points until he can find a path that will take him around the territory and finally back to Smithville. If he finds a path that doubles up he starts again. Then he checks to see if this set of flights costs less than $400.

Quick to decide but hard to find

Now Tom stumbles on to a fascinating conundrum. If he finds a new set of flights (that meet his criteria) it’s easy to confirm that it’s cheaper than $400. This aspect might be phrased in the form of “is there a set of flights cheaper than $400?” Such a question has 3 attributes:

1. It is easy to verify if a new path is cheaper
2. It is hard to find every possible path
3. There is no easy way to tell if the answer is a no (that would involve checking every possible path to make sure)

Because this involves a simple decision problem let’s rename of our acronym to TSP-DECIDE. This will help distinguish it from our next (even harder) problem.

Can we get an even better answer?

One day Tom finds another set of flights that costs $390. This makes him wonder – what is the cheapest set of flights I can take? Which is to say that he wants to optimise his trip even further. Let’s call this separate problem TSP-OPTIMIZE. Something interesting to note about this type of problem:

1. It’s at least as hard as the first problem
2. The only real way to know is to explore every single option
3. If you had a way to solve the first problem quickly it would make this problem much easier to solve
4. Suppose someone gave you an answer and said “this is the cheapest set of flights”. The only way for you to check that this was true would be to check every single possible combination yourself

Could we use a computer?

Let’s talk about Turing Machines

Tom asks “could we use a computer to solve this problem?” This presents an interesting puzzle. How do you answer a question about whether a computer is capable of solving a problem? To do this one must define exactly what a computer is in straightforward terms. Father of modern-day computing Alan Turing proposed a device called the Turing Machine. And it works like this:

• Imagine putting every instruction from the computer on a conveyor belt
• The conveyor belt delivers us instructions to process one at a time (and in order)
• Using a multicore processor: the best that they do is put more than one person on the assembly line of that conveyor belt and lurch forward 4 steps instead of one. Ultimately the instructions still have to come through one at a time. And the amount of cores you can use varies so even the jumps forward have to be instructions on the conveyor belt.

How long is a piece of Turing string?

In this line of thinking we use the letter n to denote some count of things (note: this is not the same N from NP). For example: if we have a list of things we can go through and find the 1st, 2nd, 3rd, 4th … nth item in that list. And we have a letter O (called big O notation) to represent how long something will take.

For a Turing Machine to find the nth item in a list we say that it takes O(n) time. What does this mean? If we want the 10th item in the list then it takes 10 steps down the conveyor belt to find it. How long might other things take? Here are some examples:

• Checking to see if the list is empty takes O(1) time, which means that it always takes one step. We look at the first item in the list and if there is nothing there we say it’s empty. Conversely if there is anything at all there then the list is not empty.
• If we want to look up someone’s name in the phone book we don’t need to check the whole book. To look up our salesman Tom we would start by flipping straight to the S section. Then we flip part way through and perhaps we find Stevenson. “St” means we’ve gone too far. Now we flip back a bit more until eventually we get to Smith and then Smith, T. When we narrow our information each time we look we say that it’s completed in O(log n) time.
• Looking up the nth item in a list we already know is O(n)
• Suppose you had a set of names and you wanted to sort them in Alphabetical order. You would have a list that is gradually being sorted and you would take each name one at a time and work out where it goes in the new list. This means that it takes you O(n) just to pick every name out of the unsorted set. Plus you have to spend time looking through your newly sorted list to find out where it goes. As your set of unsorted names gets smaller to search your list of sorted names gets longer. This type of sorting takes O(n²) time.

Polynomial Time, Exponential Time & Factorial Time

We call O(n²) “Polynomial Time”. Where the n squared (or raised to any power) is a polynomial. Any problem which can be solved at least that fast can be solved in polynomial time.

Suppose that you have a list of employees working in your company and every single employee is given a print out of this list. Each time a new person joins the company you have to print every single list again with the updated name. This means that for each extra item on the list you have to do the work all over again. That is to say or every n things on our Turing conveyor belt it needs to do twice as much work as when there was n-1 things on the list. This is “Exponential Time” and is represented by O(2ⁿ).

Then we get down to “Factorial Time” and is represented as O(n!). This involves such exceedingly large numbers that people often have difficulty grasping it. This bit of trivia might help illuminate how large this number is: There are so many ways to arrange a deck of playing cards that it is safe to say no two (properly) shuffled decks have ever been in the same order. That’s because there are 52! (read as 52 factorial) ways you can arrange a deck of cards.

Let’s see this problem in action:

(1) A♥, A♦, A♣, A♠, 2♥… K♠

(2) A♥, A♦, A♠, A♣, 2♥… K♠

(3) A♥, A♣, A♦, A♠, 2♥… K♠

(4) A♥, A♣, A♠, A♦, 2♥… K♠

…

(24) A♠, A♣, A♦, A♥, 2♥… K♠

From this we can see that there are 24 ways to arrange just the Aces in the deck. If you (a) shuffled 4 aces and gave them to one person and then (b) shuffled another 4 aces and gave them to another person, (c) then there is a 1 / 24 chance that they will end up in exactly the same order.

Let’s see how the odds accumulate:

• Shuffling a “one card deck” means the odds of two people getting the same deck are 100%
• With two cards it’s 1/2
• With 3 cards it’s 1/6
• With 4 cards it’s 1/24
• With 5 cards it’s 1/120
• …
• If there are 10 cards the odds are 1/3,628,800

You can see that the amount of options doesn’t double (which is exponential). In fact the odds increase by a factor of how much the size of the problem group (which is factorial). For 5 cards the factorial odds are: 1 / (1 * 2 * 3 * 4 * 5) = 1/120.

Tom’s problem (TSP-OPTIMIZE) is Factorial

It might seem that for every extra city in Tom’s territory the amount of possible trips he could take increases as a factorial:

• At 1 city we have to start the count at 0. Tom stays in Smithville and his territory involves no other cities. Therefore he has 0 possible flight options
• At 2 cities he has 1 flight option (fly there and fly back)
• At 3 cities he has 2 options (A->B->C->A and A->C->B->A)

But wait, what if there are no flights between two cities? It seems that the size of the factorial is not related to how many cities there are but how many possible flights there are. In fact we see this when there is only Smithville – there are 0 possible flight paths and that’s why there are 0 options. So Tom’s problem becomes factorially more complicated the more flight options he has to choose from.

Does P=NP?

A Non-deterministic Turing Machine

By now you will have worked out that P is Polynomial time – that is any problem which can be solved at least as fast as O(n²) or some other polynomial. But what does the N stand for in NP? This means “Non-deterministic”. And NP is a range of problems that could be solved in Polynomial time if only we had a special kind of Turing machine.

The Non-deterministic Turing Machine works like so: every time we have to make a choice between a number of options this non-deterministic machine splits itself into as many copies as there are options. In TSP we could evaluate one city at a time but each time we come to a city we get presented with a range of choices. Our hypothetical machine would replicate itself and evaluate every one of those choices at the same time. Then for each of those choices there is another set of choices and each copy would replicate itself into even more copies.

Solving in NP time

A problem is said to be NP-Complete if it it meets these criteria:

• Using this Non-deterministic Turing Machine we can solve this problem in Polynomial time
• Using a regular Turing Machine we can verify the answer in Polynomial time

If you ran our special Turing Machine over Tom’s problem it could spit out an answer and we could verify that it was true in P time (i.e. “yes, this set of flights will indeed be cheaper than $400”).

An NP-Complete solution does not need a P time evaluation of a “no” response. What does that mean? Suppose our Non-deterministic Turing Machine comes back and says “no, there are no set of flights less than $400”. There is no way that we can tell that is correct without actually going in and checking every single answer ourselves. For NP-Complete only “yes” answers need to be verifiable in P time.

When you need a Non-deterministic Turing Machine to both solve and verify the solution we call it an NP-Hard problem. An NP-Hard problem is said to be at least as hard as an NP-Complete problem but there is one other aspect to it: if we had some really easy way (called “using an oracle machine”) of solving an equivalent NP-Complete problem we could also use it to solve the NP-Hard problem efficiently.

That does sound familiar.

TSP-DECIDE is an NP-Complete problem while TSP-OPTIMIZE is NP-Hard

Tom Smith’s Problem started off so simple – “is there  (a) a set of flights cheaper than $400, (b) that visits each city only once and (c) returns me home to Smithville?” Only a computer which split itself into multiple copies every time it needs to make a decision can solve that problem efficiently.

Things got even more complicated when we asked “what is the cheapest set of flights in his territory?”. Not only would you need such a magic computer to answer that question you also need one to verify that the answer is true.

Some other problems in NP-Complete

The largest factor of the number 20 is 5. This is because 5*4 = 20 while any number larger than 5 cannot divide evenly into 20. As this number gets larger there are that many more solutions to check (n * previous number of solutions). This is of course where factorial time gets its name.

That said we’ve found tricks to make this problem easier to solve. If 20 is a factor of 100 (20*5) that means 4 is also a factor of 100 because 4 is a factor of 20. With this trick it turns out not to be such a complex task after all (unless we want to find every factor, then we are back to a factorial time problem).

In come prime numbers. Because 13 has no factors itself this makes it much harder to work with. If I asked “is 13 the largest prime factor of 1300?” how would you know? You could check all the prime numbers larger than 13 to see if they are factors of 1300 but that brings its own problems. In order to check if a number is prime you need to check its (absence of) factors. Verifying that 13 is the largest prime factor of 1300 turns out to be a complex task.

This is one of the reasons that we use prime factors in cryptography. In certain circumstances primes also allow operations to be reversible when normally this would not be possible. This lends itself to the second half of cryptography: decryption.

A trivial example is this: we know that 8/2 = 4. Yet if I give you the number 4 and ask, “what two numbers did I divide to get to 4?” you would not be able to give me an answer. That operation cannot be reversed.

Using prime numbers there is a simple cryptographyic method to exchange messages through public channels. First you have someone send a message encoded with a special key (called a public key). Though it is possible to reverse this operation it can only be done if you know the prime factor of the public key. As you’ve seen finding prime factors is an incredibly difficult task.

Once a message is encoded with a public key there is no (practical) way for this message to be decrypted except by you. You publish your public key and tell people “just encrypt all of your messages with this and send them to me, no one will be able to read them”. You can then read the message by reversing the operation with your prime based “private key”.

What happens if P=NP

Mathematicians have worked out that every NP-Complete problem is reducible to every other NP-Complete problem. This means that you can re-arrange the equations for TSP-DECIDE and it would look exactly the same as the factoring of prime numbers. Because each NP-Complete problem can be “reduced” to another NP-Complete problem, solving one solves them all.

Why not use an NP-Hard problem for cryptography?

The key strength of public key cryptography is that you can verify that a message was sent using your public key very quickly – you do this by decryption with your private key. If this could not be done efficiently then there would be no point in using the technique at all. Public key cryptography works and is reliable if and only if NP-Complete problems are hard to solve but easy to verify if you already know the answer.

Finding a way to solve NP-Complete problems

But suppose there was some trick to solving an NP-Complete problem? In the same way that we simplified finding the largest factor, maybe there is an approach to use for primes? Or what if there was a simple way to navigate a sales territory without checking every single path you could possible take? This means that any problem in NP could actually be solved in P. As such P would equal NP.

This would be good news for some but bad news for most. The infrastructure of digital security depends entirely on the assumption that P≠NP.

The current view of P vs NP

In an almost poetic way the answer to the question does P=NP could be verified easily if the answer is yes. All you would have to do is find a single solution to an NP-Complete problem and the proof would be relatively simple to verify. Yet if the answer to the question is “no” then any attempts to search for solutions to NP-Complete problems are ultimately pointless.

It’s worth noting that we have not found a way to verify that P≠NP.

My Haskell TSP Solver

From my ongoing Machine Learning research I’ve found various approximate solutions to this problem. Using the mechanics of an Ant Colony it’s possible to find approximate solutions to the Travelling Salesman Problem. I’ve recently learned Haskell and wrote an Ant Colony Optimisation Algorithm. The code is open source and available for download for those that are curious.