Editing 287: NP-Complete

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

==Explanation==
Another entry in the "[[My Hobby]]" series of comics. [[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) that 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 {{w|Computational complexity theory|computational complexity theory}}, NP stands for "nondeterministic polynomial time," which means that problems that are NP take polynomial running time (i.e. the time a CPU would take to run the program would be polynomial in the input size) to verify a solution, but it is unknown whether finding any or all solutions can be done in polynomial time. Polynomial time is considered efficient; exponential and higher times are considered unfeasible for computation. NP-complete problems are ones that, if a polynomial time algorithm is found for any of them, then all NP problems have polynomial time solutions. In short, particular guesses in NP-complete problems can be checked easily, but systematically finding solutions is far more difficult.

The waiter's problem is NP-complete, since a given order's price can be found and checked quickly, but finding an order to match a price is much harder. This causes the order to effectively be an {{w|application layer}} {{w|denial-of-service attack}} / {{w|algorithmic complexity attack}} on the waiter, similar to {{w|Slowloris (computer security)|Slowloris}} or {{w|ReDoS}}. (Formal proofs of the NP-completeness of the knapsack problem can be found at the above link.) The most straightforward way for a human 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|travelling salesman problem}}, mentioned by Cueball at the end, referring to the waiter's claim that he has 6 more tables to get to. (see also [[399: Travelling Salesman Problem]]).

The title text refers to the fact that NP-complete problems have no known polynomial time general solutions, and it is unknown if such a solution can ever be found. 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 (including proving that such a solution doesn't exist) is worth US$1,000,000. A 50% tip is slightly less than fair.

For those curious, there are exactly two combinations of appetizers that total $15.05 and solve the problem posed in the comic strip:
#A combination of two orders of hot wings, one order of mixed fruit, and one sampler plate
#Seven mixed fruit orders (this solution was not intended - see [[#Trivia|trivia]] below)

==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
:Sandwiches
::Barbecue 6.55
:[Megan, another person, and Cueball are sitting at a table. Cueball is holding the menu as well as a thick book and is ordering from a waiter. Megan is facepalming.]
:Cueball: We'd like exactly $15.05 worth of appetizers, please.
:Waiter: ...Exactly? Uhh...
:Cueball: Here, these papers on the knapsack problem might help you out.
:Waiter: Listen, I have six other tables to get to—
:Cueball: —As fast as possible, of course. Want something on traveling salesman?

==Trivia==

*"Chotchkies" (slightly misspelt) is Yiddish slang for little accessories and trinkets. It is also the name of the restaurant in the 1999 Mike Judge-directed comedy ''{{w|Office Space}}''.

*In [http://www.maa.org/mathhorizons/MH-Sep2012_XKCD.html an interview] with the Mathematical Association of America, Randall said that the trivial answer to this problem was a mistake.

{{comic discussion}}
[[Category:Comics featuring Cueball]]
[[Category:My Hobby]]
[[Category:Comics with color]]
[[Category:Math]]
[[Category:Programming]]