NPComplete  Why So Hard? 
Written by Mike James 
Sunday, 11 March 2012 
This week's selected xkcd cartoon is about the mysteries of NPComplete 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 Nondeterministic 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 nondeterministic, 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 NPComplete problems? An NPComplete 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 NPComplete problem, then you have a P algorithm for all NP problems and NP=P. You can think of an NPComplete problem as being a universal representative of NP problems. Finally what about NPHard problems? An NPHard problem is any problem, not necessarily in NP that can be reduced to an NPcomplete problem in a reasonable i.e polynomial time. In this sense NPHard problems are as least as hard as NP problems but they could be harder. For example, suppose you have an exponential solution to an NPhard 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 NPhard because it gives you the solution to the NPcomplete 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: 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 NPComplete 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 bistromathematics overly much. But I still doubt that this party of computer scientists will ever get fed.
Further Reading Computational Complexity
Comments
or email your comment to: comments@iprogrammer.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.

Last Updated ( Monday, 12 March 2012 ) 