This week's selected xkcd cartoon is about the mysteries of NP-Complete problems. So does the waiter have a problem? Probably not. Let's see why.

Algorithms take different amounts of time to complete their tasks, but what really matters in complexity theory is how they scale.

The travelling salesman problem is one mentioned in the cartoon, but if I give you a sample problem you can probably solve it in a reasonable time. All you have to do is find a route for the salesman so that they visit each city just once with a total distance less than L. (Note the full problem asks for L to be a minimum, but this is an even harder problem)

Of course for a few cities this is easy - just work out each possible route and pick a route with a distance less than L. The point about the problem is that each time you add a city the number of routes you have to examine grows ever bigger. The increase in the work needed goes up out of all proportion to the apparent increase in the size of the problem.

What this means is that soon or later you reach a point where a reasonable size problem is widely out of your computational power. So, for example, if I ask you to find a shortest path between even 100 cities you have a lot of work to do.

But there is an interesting other side to many such problems. For example, if I give you a proposed solution to even the 100 city problem you can check that it is a solution very quickly - just confirm it visits each city and that the distance travelled is less than L.

This is what makes the problem NP.

The N means Non-deterministic and the P is polynomial and the idea is that while the difficulty of the original problem may grow faster than any power of the size (i.e. it grows faster than any polynomial of the size) checking a solution that is arrived at by guessing, i.e non-deterministic, is polynomial in problem size.

It is this reduction to a P problem by guessing a solution that leads many to think that NP=P. That is, there are quicker solutions to NP problems that we just haven't found yet.

So what are NP-Complete problems?

An NP-Complete problem is one that can be converted into any other NP problem in a reasonable, i.e. a polynomial amount of time. So if you have a P algorithm for any NP-Complete problem, then you have a P algorithm for all NP problems and NP=P.

You can think of an NP-Complete problem as being a universal representative of NP problems.

Finally what about NP-Hard problems?

An NP-Hard problem is any problem, not necessarily in NP that can be reduced to an NP-complete problem in a reasonable i.e polynomial time. In this sense NP-Hard problems are as least as hard as NP problems but they could be harder. For example, suppose you have an exponential solution to an NP-hard problem then it can be converted into an exponential solution to an NP problem (the polynomial time part just gets swallowed by the exponential) and you have an exponential time solution to the NP problem - but the NP problem might have another solution that works in polynomial time.

For example the full travelling salesman problem, finding the shortest path, is NP-hard because it gives you the solution to the NP-complete problem of finding a path shorter than L. However the problem of finding a path less than L might be an easier problem than finding the minimum path.

The important point here is that in most cases they are harder and hence form an even more difficult class of problems.

So now back to the xkcd cartoon:

(click to enlarge)

The problem the waiter is being asked to solve is to find a combination of items from the menu that cost exactly $15.05.

This is a version of the Knapsack problem which is known to be NP-Complete and so if the problem is big enough it takes a long time to solve but once again a proposed solution can be checked very quickly.

So is the waiter doomed to spend all eternity searching for a solution?

Not with a menu of the sort of size shown. Sadly, despite the cartoons best intent to overload the waiter, it is doubtful that it would tax his bistro-mathematics overly much.

But I still doubt that this party of computer scientists will ever get fed.

Further Reading

The Knapsack problem

Computational Complexity
Computability
Classic Nintendo Games Are NP Hard
Physics Is NP Hard
No 16-Clue Sudoku!
Pancake flipping is hard - NP hard

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.