Talk:287: NP-Complete

Explain xkcd: It's 'cause you're dumb.
Revision as of 19:11, 14 May 2014 by Dgbrt (talk | contribs)
Jump to: navigation, search

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)


Roman Czyborra did post this at the explain:

The Solution

… can be calculated as

let totaling total menu = if total == 0 then [[]]
 else if total < 0 || null menu then []
 else totaling total (tail menu) ++ map (
 head menu :) (totaling (total - head menu) menu)
in totaling 1505 [215,275,335,355,420,580]
== [[215,355,355,580],[215,215,215,215,215,215,215]]

I don't think this is a helpful explain. --Dgbrt (talk) 19:11, 14 May 2014 (UTC)