explain xkcd - User contributions [en]

288: Elevator

2012-08-07T20:29:53Z

Mathman: /* Description */

{{comic
| number = 288
| date = July 11, 2007
| title = Elevator
| image = Elevator.jpg
| imagesize =
| titletext = Quick, try it with 'LOVE'.
}}

== Image Text ==
Quick, try it with 'LOVE'.

== Description ==
Cueball is in an elevator, and notices that, beneath the certificate of inspection mandatory in all U.S. elevators at least, there are buttons for Floor 1, 2, 3, and 4, and then a mysterious unlabeled button. Possible logical conclusions he might have made include (1) there is a fifth floor (reachable by pushing the bottom button) which for some reason is not labeled; (2) the button has some other function (a common one is to stop the elevator wherever it may be, whether exactly aligned with a floor or not) but again, is mistakenly not labeled; or (3) the panel with the buttons is from a template used for various elevators with up to five floors, and as this particular elevator only goes to four floors the bottom button is unlabeled and nothing will happen if he pushes it.

He has, however, chosen to accept a different explanation: the fifth button is not currently assigned, but giving it a label will assign it to whatever floor (or other function) he can give it. The possibilities are truly endless. And so, the intrepid Cueball writes “Zeppelin” on a slip of paper, tapes it next to the unassigned button, thereby assigning it to move the elevator not to Floor 3 or Floor 5 but to Zeppelin. And it works – the elevator opens aboard a zeppelin (or dirigible or airship or blimp) floating in the air, high above a land with many lakes (perhaps Minnesota, the “Land of 10,000 Lakes.”)

The image text is most likely a reference to the Aerosmith song “Love in an Elevator,” which really is about sex in an elevator. However, it would also be great if one could reach the elevation of love by getting there in a magic elevator.

288: Elevator

2012-08-07T20:29:11Z

Mathman: /* Description */

{{comic
| number = 288
| date = July 11, 2007
| title = Elevator
| image = Elevator.jpg
| imagesize =
| titletext = Quick, try it with 'LOVE'.
}}

== Image Text ==
Quick, try it with 'LOVE'.

== Description ==
Cueball is in an elevator, and notices that, beneath the certificate of inspection mandatory in all U.S. elevators at least, there are buttons for Floor 1, 2, 3, and 4, and then a mysterious unlabeled button. (Possible logical conclusions he might have made include (1) there is a fifth floor (reachable by pushing the bottom button) which for some reason is not labeled; (2) the button has some other function (a common one is to stop the elevator wherever it may be, whether exactly aligned with a floor or not) but again, is mistakenly not labeled; or (3) the panel with the buttons is from a template used for various elevators with up to five floors, and as this particular elevator only goes to four floors the bottom button is unlabeled and nothing will happen if he pushes it.

He has, however, chosen to accept a different explanation: the fifth button is not currently assigned, but giving it a label will assign it to whatever floor (or other function) he can give it. The possibilities are truly endless. And so, the intrepid Cueball writes “Zeppelin” on a slip of paper, tapes it next to the unassigned button, thereby assigning it to move the elevator not to Floor 3 or Floor 5 but to Zeppelin. And it works – the elevator opens aboard a zeppelin (or dirigible or airship or blimp) floating in the air, high above a land with many lakes (perhaps Minnesota, the “Land of 10,000 Lakes.”)

The image text is most likely a reference to the Aerosmith song “Love in an Elevator,” which really is about sex in an elevator. However, it would also be great if one could reach the elevation of love by getting there in a magic elevator.

288: Elevator

2012-08-07T20:27:12Z

Mathman: fixed link to comic

288: Elevator

2012-08-07T20:25:05Z

Mathman: created stub

{{comic
| number = 288
| date = July 11, 2007
| title = Elevator
| image = Elevator.png
| imagesize =
| titletext = Quick, try it with 'LOVE'.
}}

== Image Text ==
Quick, try it with 'LOVE'.

== Description ==

287: NP-Complete

2012-08-07T19:33:14Z

Mathman: /* Description */

{{comic
| number = 287
| date = July 9, 2007
| title = NP-Complete
| image = Np_complete.png
| imagesize =
| titletext = General solutions get you a 50% tip.
}}

== Image Text ==
General solutions get you a 50% tip.

== Description ==
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 [[wikipedia:Knapsack_problem|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, [[wikipedia:NP-complete|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 (15) 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 (1709) 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 [[wikipedia:Millennium_Prize_Problems|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.

Another famous NP-complete problem is the [[wikipedia:Travelling_salesman_problem|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 [[wikipedia:Office_Space|Office Space]]. (In that film, the character Joanna, played by [[wikipedia:Jennifer Aniston|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: either (1) seven mixed fruit orders, or (2) a combination of two orders of hot wings, one order of mixed fruit, and one sampler plate.

[[Category:My Hobby]]

287: NP-Complete

2012-08-07T19:32:38Z

Mathman:

{{comic
| number = 287
| date = July 9, 2007
| title = NP-Complete
| image = Np_complete.png
| imagesize =
| titletext = General solutions get you a 50% tip.
}}

== Image Text ==
General solutions get you a 50% tip.

== Description ==
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 [[wikipedia:Knapsack_problem|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, [[wikipedia:NP_complete|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 (15) 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 (1709) 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 [[wikipedia:Millennium_Prize_Problems|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.

Another famous NP-complete problem is the [[wikipedia:Travelling_salesman_problem|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 [[wikipedia:Office_Space|Office Space]]. (In that film, the character Joanna, played by [[wikipedia:Jennifer Aniston|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: either (1) seven mixed fruit orders, or (2) a combination of two orders of hot wings, one order of mixed fruit, and one sampler plate.

[[Category:My Hobby]]

Category:My Hobby

2012-08-07T19:25:32Z

Mathman: Created page with "These are all the comics with a title at the top stating "My Hobby:""

These are all the comics with a title at the top stating "My Hobby:"

287: NP-Complete

2012-08-07T19:22:31Z

Mathman:

287: NP-Complete

2012-08-07T19:19:50Z

Mathman: page created as stub