Editing 287: NP-Complete
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 8: | Line 8: | ||
==Explanation== | ==Explanation== | ||
− | Another entry in the | + | {{incomplete|The "In computational complexity theory" still needs a review}} |
+ | Another entry in the “My Hobby” series of cartoons. [[Cueball]] is embedding {{w|NP-complete|NP-complete problems}} in restaurant orders. Specifically, he is ordering appetizers not by explicitly stating the names, but by the total price of them all. This is a simplified example of the {{w|Knapsack problem|knapsack problem}}. This is a problem in combinatorial optimization, as follows: If you have a knapsack (backpack or rucksack) which can hold a specific amount of weight, and you have a set of items, each with its own assigned value and weight, you have to select items to put into the knapsack so that the weight does not exceed the capacity of the knapsack and the combined value of all the items is maximized. | ||
− | In | + | 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 is to methodically start by first listing all the (6) ways of choosing one appetizer, and their total costs, then list all the (21) ways of choosing two appetizers (allowing repeats), 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. |
− | + | Another famous NP-complete problem is the {{w|Travelling Salesman problem}}, mentioned by Cueball at the end (see also [[399: Travelling Salesman Problem]]). | |
− | + | The title text refers to the fact that NP-complete problems have no known general solutions. If the waiter can find an efficient general solution to this he will have solved one of the most famous problems in mathematics. This problem is one of the six remaining unsolved {{w|Millennium Prize Problems}} stated by the Clay Mathematics Institute in 2000, for which a correct solution is worth US$1,000,000. A 50% tip is slightly less than fair. | |
− | The | + | ;The 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== | ==Transcript== | ||
Line 26: | Line 26: | ||
:Embedding NP-Complete problems in restaurant orders | :Embedding NP-Complete problems in restaurant orders | ||
:[A menu is shown.] | :[A menu is shown.] | ||
− | : | + | :Chotchkies Restaurant |
:Appetizers | :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, including Cueball who is ordering from a waiter.] | |
− | |||
− | :[ | ||
:Cueball: We'd like exactly $15.05 worth of appetizers, please. | :Cueball: We'd like exactly $15.05 worth of appetizers, please. | ||
:Waiter: ...Exactly? Uhh... | :Waiter: ...Exactly? Uhh... | ||
:Cueball: Here, these papers on the knapsack problem might help you out. | :Cueball: Here, these papers on the knapsack problem might help you out. | ||
− | :Waiter: Listen, I have six other tables to get | + | :Waiter: Listen, I have six other tables to get to- |
− | :Cueball: | + | :Cueball: -As fast as possible, of course. Want something on traveling salesman? |
==Trivia== | ==Trivia== | ||
− | + | *A film reference is embedded in the menu in the first panel: The restaurant is called “Chotchkies”, a fictional restaurant featured in the film {{w|Office Space}}. In that film, the character Joanna, played by {{w|Jennifer Aniston}}, quits her job at Chotchkies, a typical family-oriented chain restaurant, over their policy that she wear a large number of tchotchkes, or “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. | |
− | * | ||
− | |||
− | |||
{{comic discussion}} | {{comic discussion}} | ||
Line 53: | Line 48: | ||
[[Category:My Hobby]] | [[Category:My Hobby]] | ||
[[Category:Comics with color]] | [[Category:Comics with color]] | ||
− | |||
− |