287: NP-Complete

Explain xkcd: It's 'cause you're dumb.
Revision as of 04:28, 2 January 2013 by Davidy22 (Talk | contribs)

Jump to: navigation, search
NP-Complete
General solutions get you a 50% tip.
Title text: General solutions get you a 50% tip.

Explanation

Another entry in the “My Hobby” series of cartoons; here, Cueball is embedding NP-complete problems in restaurant orders. Specifically, he is ordering appetizers not by explicitly stating the names of the appetizers, but by the total price of the chosen appetizers. This is a (simplified) example of the knapsack problem. The knapsack (or rucksack) problem is a problem in combinatorial optimization, as follows: if you have a knapsack (or backpack, or rucksack, as your regional desire to call it may be) which can hold a specific amount of weight, and you have a set of items, each with its own assigned value and weight, can you select items to put into the knapsack so that (1) the weight does not exceed the capacity of the knapsack, and (2) the combined value of all the items is maximized. (The example in this cartoon is simplified, because we are not given the corresponding “value” of each item – like we would be if, for example, Cueball and his two friends assigned a perceived value of 7 on a scale of 1 to 10 for getting hot wings, but only a 2 out of 10 for a side salad. Another way to introduce complexity into the problem would be if the patrons were considering the calorie values of each appetizer on the menu.)

The knapsack problem is, as indicated by the title of the strip, NP-complete. In computational complexity theory, NP stands for “nondeterministic polynomial time.” Basically, for an NP-complete problem, there is no efficient way to find a solution, but it is relatively easy to verify that a solution works. Conceptually, for the problem posed in this comic, the most straightforward way to find a solution (not even knowing for certain if there is one) is to methodically start by first listing all the (6) ways of choosing one appetizer, and their totals (which of course are the prices of each appetizer), then list all the (21) ways of choosing two appetizers (allowing the same appetizer to be chosen twice, since we are assuming that the chef can create more than one sampler platter), and then list all the (56) ways of choosing three appetizers, and so forth. As any combination of eight appetizers would be more than $15.05, the process need not extend beyond listing all the (1715) ways of choosing seven appetizers.

The image text refers to the fact that NP-complete problems have no known general solution. (A general solution would be the optimal solution to this problem generalized to allow any prices for the appetizers.) If the waiter can find an efficient general solution to this, or any NP-complete problem, he will have solved one of the most famous problems in computer science, whether or not P=NP. In other words, if every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. This problem is one of the seven Millennium Prize Problems stated by the Clay Institute in 2000, six of which (including whether P=NP) are still unsolved, for which a correct solution is worth US$1,000,000, so a 50% tip is slightly less than fair.

Another famous NP-complete problem is the Travelling Salesman problem (also see 399: Travelling Salesman Problem), also mentioned in the strip. An example: suppose a traveling salesman has to visit ten cities and then return home, and it is possible to directly travel from any city to any other city (by plane, for example.) What is the minimum distance (or time, or cost) necessary for the trip? Like the knapsack problem, it is (usually) difficult to find the best solution without trying a very large number of combinations. Cueball mentions this problem after the waiter states he has to tend to six other tables.

A film reference is embedded in the menu in the first panel: the restaurant is called “Chotchkies,” a fictional restaurant featured in the film Office Space. (In that film, the character Joanna, played by Jennifer Aniston, quits her job at Chotchkies, a typical family-oriented chain restaurant, over their policy that she wear a large number of “flair” items – tacky pins, buttons, or other adornments to a worker’s uniform which can often be seen on waiters and waitresses at chain family restaurants, as well as those who work at movie theaters or large retail chain stores.)

Solution

There are exactly two solutions to the problem posed in the comic strip, combinations of appetizers which total $15.05:

  • seven mixed fruit orders
  • a combination of two orders of hot wings, one order of mixed fruit, and one sampler plate

Transcript

My Hobby:
Embedding NP-Complete problems in restaurant orders
[A menu is shown]
Chotchkies Restaurant
Appetizers
Mixed Fruit 2.15
French Fries 2.75
Side Salad 3.35
Hot Wings 3.55
Mozzarella Sticks 4.20
Sampler Plate 5.80
[Three people sit at a table. One man at the table is ordering from a waiter]
Man at table: We'd like exactly $15.05 worth of appetizers, please.
Waiter: ... Exactly? Uhh ...
Man at table: Here, these papers on the knapsack problem might help you out.
Waiter: Listen, I have six other tables to get to -
Man at table: - As fast as possible, of course. Want something on traveling salesman?
Comment.png add a comment!

Discussion

Shame this only works in restaurants that price all their appetizers differently. Davidy22 (talk) 03:18, 13 October 2012 (UTC)

I have a hunch that the seven fruit cups are pretty intentional as the first item on the menu and the simplest solution possible. I was about to write a script to solve the problem through random selections and was going to optimize for speed by limiting the maximum times an item could be order to floor(15.05/price). Thus, one could order up to 2 sample plates, 3 moz sticks, 5 of the hot wings/side salad/french fries or 7 fruit cups without going over budget. (side note: you can always with these prices squeeze in a fruit cup with the exception of the 7 fruit cups). I found the "trivial" solution on the first step of the "preliminary" work for that script and then took a catnap. Of course, since the nontrivial solution involves the same item as the trivial solution, one could just pick a number, multiply by that number, subtract one unit, and pick two other items, whose prices were not set yet, and adjust their prices to add up accordingly just to ensure both trivial and nontrivial solutions lest anyone actually write a program to solve the problem through brute force as oppose to through wit. Why seed? Because to not have a nontrivial solution would be so much like Blackhat. Note to self: try this sometime in the real world using a real menu. Katya (talk) 02:17, 23 November 2012 (UTC)

Note: Traveling Salesman Problem might be mentioned also because both this problem and the Knapsack problem to be solved belong to set of NP-complete problems; a Knapsack problem can be transformed in polynomial time to Traveling Salesman Problem, and solution of Traveling Salesman Problem can be transformed in polynomial time to Knapsack problem solution. --JakubNarebski (talk) 16:00, 11 December 2012 (UTC)


In an interview with the Mathematical Association of America Randall said that the trivial answer to this problem was a mistake. Xrays Knock Charms Down (talk) 03:00, 6 May 2013 (UTC)

I added this very interesting info to the explanation - at first as a trivia, but then I realized that it would not be seen by everyone - as you often do not read below the transcript. Why would you, you do not need to see what was in the comic again... So I moved it up to the solution part, because to me it is a very important fact about this comic. An error by Randall... But Dgbrt keeps moving this info away from the solution. I have understood now that the trivia should be below the transcript - although I cannot see why this should be so - as I have just described. But who says that this info should be a trivia item? It was I who put it there (by mistake?) at first. I will try not to start an editing fight here, but still think there should at least be a mention in the explanation that it was a mistake - in case you do not realize there is a trivia section below. I have used this page a lot lately, and had not found out before, that it was always below. There is not that many pages with trivia sections Kynde (talk) 11:02, 10 March 2014 (UTC)


I was bored and tried to find a solution for fun. I found the more complex one quite fast by chance. It was actually the second combination I tried. I did not realize you could just add seven fruit cups because I was so set on starting with the sampler plate. Now I am not sure if I should be glad, because I was so lucky, or annoyed that my fight-the-boredom-idea did not work out, or even more annoyed that I never have that kind of luck in the lab where I could really use it for finding the one thing out of a thousand possible causes for "why-does-my-experiment-not-work" which actually will give me some usable data. 84.56.77.11

This explanation is thorough, and I like being thorough, but it seems to be a bit of overkill. I copy-edited it a bit, but I have a couple qualms. This is not really the knapsack problem, as it does not attach values to the items (as mentioned). It is more of a subset sum problem, which admittedly could be considered a variant of the knapsack problem. Secondly, I don't see why we need to go into detail about the movie Office Space. --Quicksilver (talk) 18:34, 22 August 2013 (UTC)

I did some clean-ups, but the the "In computational complexity theory" still needs a review.--Dgbrt (talk) 20:19, 22 August 2013 (UTC)

Inspired by this comic, somebody has actually created an ordering site which tries to give you an order from a restaurant in your area (US only I think) totalling a specific amount NP Food. Worth including above? -- Copito (talk) 20:43, 8 November 2013 (UTC)

That site doesn't work for me. —TobyBartels (talk) 10:07, 19 November 2013 (UTC)
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox

It seems you are using noscript, which is stopping our project wonderful ads from working. Explain xkcd uses ads to pay for bandwidth, and we manually approve all our advertisers, and our ads are restricted to unobtrusive images and slow animated GIFs. If you found this site helpful, please consider whitelisting us.

Want to advertise with us, or donate to us with Paypal or Bitcoin?