I came across the following article which presents the problem:
A group of people walk into a restaurant and want to spend exactly
$15.05 on appetizers. They also want them as fast as possible. This
leaves waiter with an NP-hard problem to solve, a variation of
knapsack problem.
The article goes on to create some sort of “genetic algorithm” to solve the problem. My question is, is that really necessary?
First of all, no programming solution would be possible if no combination of existing appetizers could equal $15.05. Right?
Also, if I were approached with this problem, I would do something like this:
// loop through appetizers
// deduct price from total amount ($15.05) until the difference <= zero
// add to new array of appetizers
// sort the new appetizers array by "time to make the appetizer"
// return new appetizers array
Isn’t it that simple? Thanks for your review.
5
As others have mentioned, the trick is that they must spend exactly $15.05, which does indeed make this an NP-hard problem similar to the knapsack problem. However, “NP-hard” doesn’t necessarily mean “hard to solve in practice” — if the number of appetizers is small, then a brute force solution is relatively easy to code up and will work just fine. We can say with some degree of certainty that we don’t think there is any algorithm possible that can quickly solve the problem as the number of appetizers on the menu increases. If you want to handle the problem for arbitrarily sized menus, then you have two choices:
-
Approximation methods (usually deterministic) that are often guaranteed to find a solution within some constant factor of the best solution in polynomial time.
-
Heuristics (we usually call them metaheuristics) that simply try their best to come up with the best thing they can find.
Genetic algorithms are an example of the latter approach. You have no guarantees at all about what a GA will do, but empirically, they usually work reasonably well. You probably won’t get the best solution, but you’ll likely get something decent.
Each approach has advantages and disadvantages, but unless P=NP, which essentially all computer scientists doubt, but for which providing a proof is one of the foremost unsolved problems in mathematics, then we know you’ll need to do something clever to try and find a solution via some method that will likely fail to find the perfect solution, or perhaps even any solution at all. Such is life in NP-hard land.
The very basics of complexity theory
Suppose you are given a problem with a yes/no answer. For instance, “Given these menu items, is there a subset that adds up to exactly $15.05 in cost?” We call these decision problems, and we can classify them according to how hard they are to solve. (For technical reasons, we tend to consider only decision problems, but optimization problems can be converted to an equivalent decision problem easily enough, so the basic principles are the same).
Let the set P be the set of all such problems for which we can find a solution “easily”. OK…seems simple enough. We just need to define what we mean by “easily”. The basic distinction here is between polynomial and exponential time. Note that so far, we’ve only considered a general class of problems — problems where there’s a menu and items on it. Any particular instance of the problem might be trivial. Suppose the menu only has one item and it costs $16. Then that instance is easy. What we’re after here is a general notion of difficulty based on the size of the problem instance. If the menu has K items, how long will the best algorithm take to solve it as a function of K? If that function has K in an exponent, then we say the algorithm requires exponential time. Otherwise, we have a polynomial time algorithm.
Back to the class P now. P is the class of problems for which we know of an algorithm that can solve any instance of any problem in P in polynomial time.
This brings us to the class NP. You’d think this meant “non-polynomial” time, but that’s not actually right. In fact, it’s the class of problems that can solved in polynomial time by an algorithm that can use a non-deterministic oracle. That’s a fancy way of saying, “if there’s a magic 8-ball that could tell you the answer, could you at least prove the answer was correct in polynomial time?”
Take that appetizer menu problem again. We don’t see an obvious algorithm for solving it in polynomial time, but if I tell you that taking items A, B, and C is a valid solution, it’s really easy to add up their prices and verify that. Problems for which this is true make up the class NP.
It should be easy to see that any problem in P is also in NP (remember these are sets, so notions of “in” just mean that there’s a subset relationship). However, we don’t know whether P is a proper subset of NP. If not, then P = NP; if so, then P!=NP.
This has still been fairly academic, but we can translate this to simple English. The question of whether P=*NP* is the question of whether any problem for which a solution can be recognized quickly also has the property that the solution can be found quickly. Mathematicians would state this as “is finding a proof harder than verifying a proof that is given to you?”
No one knows the answer to this question, but it is almost universally believed that P!=NP — that is, that there are problems for which there exists no efficient way of finding the solution, even if a solution can be verified quickly.
We can go further than this. One very useful idea is that of NP-completeness. NP-Complete is another class, just like P and NP. In fact, it is a subset of NP that contains only problems that are at least as hard as every problem in NP. What that means is that if you have an unknown problem and you want to know whether there’s a polynomial time algorithm for it, one thing you can do is to try to reduce any problem in NP-complete to your problem (with the reduction being capable of being done in polynomial time as well). If you can find a way of transforming your problem into, say the traveling salesperson problem (which we know to be in NP-complete) then any algorithm that could solve your problem could also solve the TSP. And by the definition of NP-complete, could therefore solve every problem in NP. Because we by now think this is extraordinarily unlikely to happen, it’s very strong evidence that your problem is not efficiently solvable.
This is I think the most practically applicable thing to know about complexity theory. There are hundreds, maybe thousands, of known NP-hard and NP-complete problems (note: NP-hard is like NP-complete, only the problems don’t have to be in NP themselves) . Knowing a little bit about these ideas can be a really useful trigger. If your boss wants you to solve some problem and you’re aware of these basic ideas, you may be able to say, “Hang on, this looks an awful lot like the subset-sum problem, and I think that was NP-complete. Maybe I need to look at heuristic approaches,” instead of bailing right in and trying something that’s doomed to fail.
4