explain xkcd - User contributions [en]

Talk:3226: Home Solar

2026-03-30T22:00:56Z

WikipedianPolitician: signature

Beep Boop [[Special:Contributions/216.25.182.141|216.25.182.141]] 21:49, 30 March 2026 (UTC)

Black Hat, because who else??? [[Special:Contributions/64.201.132.210|64.201.132.210]] 21:52, 30 March 2026 (UTC)

Title text may refer to policy decisions in the second Trump administration which promote the use of fossil fuels or undo existing policies which promote the use of renewables. The burning of industrial waste in his front yard may or may not be an oblique reference to the environmental damage being done in the current war in Iraq, in which petroleum-processing facilities and ships containing oil are being set on fire. [[Special:Contributions/64.201.132.210|64.201.132.210]] 21:56, 30 March 2026 (UTC)
:Possible, and logical. Let's not ignore the possibility that this is just random environmental activism from Randall though, like what he seems to be exhibiting in xkcd #2948. [[User:WikipedianPolitician|WikipedianPolitician]] ([[User talk:WikipedianPolitician|talk]]) 22:00, 30 March 2026 (UTC)

Talk:3226: Home Solar

2026-03-30T22:00:33Z

WikipedianPolitician: reply comment

3226: Home Solar

2026-03-30T21:57:07Z

WikipedianPolitician: minor correction

{{comic
| number = 3226
| date = March 30, 2026
| title = Home Solar
| image = home_solar_2x.png
| imagesize = 740x258px
| noexpand = true
| titletext = "While I try to do my part to destroy the environment, I try not to focus too much on individual responsibility. By pushing for broad policy changes, we can collectively do far more damage to the biosphere than any of us could on our own."
}}

==Explanation==
{{incomplete|This page was created recently. Don't remove this notice too soon.}}
Black Hat and Cueball are outside Black Hat's house (presumably) discussing the solar panels he has recently installed on the roof. Cueball asks why he has done this, as he claims Black Hat has described himself as anti-renewable. Black Hat responds that, as much as he'd prefer an option that harmed the planet more, solar power is simply the cheapest option and his budget is incapable of supporting anything else.

Black Hat in the end claims that he can try to 'make up for this' by buying industrial waste with the saved money and burning it in his backyard. Cueball responds with a knowing comment about 'carbon onsets'. This is a play on carbon ''offsets'', certificates won for lowering one's carbon footprint.

==Transcript==
{{incomplete transcript|Don't remove this notice too soon.}}
:[Black Hat and Cueball stand next to a house with solar panels on the roof]
:Cueball: Wait, you got solar panels? I thought you were against renewables.
:[Black Hat and Cueball are still discussing]
:Black Hat: Oh, Definitely. I hate the environment and want to harm it as much as possible.
:Black Hat: I'd '''Love''' to have an oil furnace.
:[Zoom on Black Hat]
:Black Hat: But the technology just isn't there and the cost is too high.
:Black Hat: I despise solar, but it makes more financial sense in my situation.
:[Return to previous zoom]
:Black Hat: But with the money I'm saving, I can buy and burn industrial waste in my yard to try to make up for it.
:Cueball: Ah, yeah, carbon onsets.

{{comic discussion}}<noinclude>

3226: Home Solar

2026-03-30T21:56:37Z

WikipedianPolitician: correction to explanation

{{comic
| number = 3226
| date = March 30, 2026
| title = Home Solar
| image = home_solar_2x.png
| imagesize = 740x258px
| noexpand = true
| titletext = "While I try to do my part to destroy the environment, I try not to focus too much on individual responsibility. By pushing for broad policy changes, we can collectively do far more damage to the biosphere than any of us could on our own."
}}

==Explanation==
{{incomplete|This page was created recently. Don't remove this notice too soon.}}
Black Hat and Cueball are outside Black Hat's house (presumably) discussing the solar panels he has recently installed on the roof. Cueball asks why he has done this, as he claims Black Hat has described himself as anti-renewable. Black Hat responds that, as much as he'd prefer an option that harmed the planet more, solar power is simply the cheapest option and his budget is incapable of supporting anything else.

Black Hat in the end claims that he can try to 'make up for this' by buying industrial waste with the saved money and burning it in his backyard. Cueball responds with a knowing comment about 'carbon onsets'. This is a play on carbon ''offsets'', a certificate won for lowering one's carbon footprint.

==Transcript==
{{incomplete transcript|Don't remove this notice too soon.}}
:[Black Hat and Cueball stand next to a house with solar panels on the roof]
:Cueball: Wait, you got solar panels? I thought you were against renewables.
:[Black Hat and Cueball are still discussing]
:Black Hat: Oh, Definitely. I hate the environment and want to harm it as much as possible.
:Black Hat: I'd '''Love''' to have an oil furnace.
:[Zoom on Black Hat]
:Black Hat: But the technology just isn't there and the cost is too high.
:Black Hat: I despise solar, but it makes more financial sense in my situation.
:[Return to previous zoom]
:Black Hat: But with the money I'm saving, I can buy and burn industrial waste in my yard to try to make up for it.
:Cueball: Ah, yeah, carbon onsets.

{{comic discussion}}<noinclude>

3226: Home Solar

2026-03-30T21:55:09Z

WikipedianPolitician: Added another piece to the explanation (new page, so I'm going slow to avoid edit conflicts)

{{comic
| number = 3226
| date = March 30, 2026
| title = Home Solar
| image = home_solar_2x.png
| imagesize = 740x258px
| noexpand = true
| titletext = "While I try to do my part to destroy the environment, I try not to focus too much on individual responsibility. By pushing for broad policy changes, we can collectively do far more damage to the biosphere than any of us could on our own."
}}

==Explanation==
{{incomplete|This page was created recently. Don't remove this notice too soon.}}
Black Hat and Cueball are outside Black Hat's house (presumably) discussing the solar panels he has recently installed on the roof. Cueball asks why he has done this, as he claims Black Hat has described himself as anti-renewable. Black Hat responds that, as much as he'd prefer an option that harmed the planet more, solar power is simply the cheapest option and his budget is incapable of supporting anything else.

Black Hat in the end claims that he can try to 'make up for this' by buying industrial waste with the saved money and burning it in his backyard. Cueball responds with a knowing comment about 'carbon onsets'. This is a play on carbon ''offsets'', attempts at lowering one's net carbon footprint.

==Transcript==
{{incomplete transcript|Don't remove this notice too soon.}}
:[Black Hat and Cueball stand next to a house with solar panels on the roof]
:Cueball: Wait, you got solar panels? I thought you were against renewables.
:[Black Hat and Cueball are still discussing]
:Black Hat: Oh, Definitely. I hate the environment and want to harm it as much as possible.
:Black Hat: I'd '''Love''' to have an oil furnace.
:[Zoom on Black Hat]
:Black Hat: But the technology just isn't there and the cost is too high.
:Black Hat: I despise solar, but it makes more financial sense in my situation.
:[Return to previous zoom]
:Black Hat: But with the money I'm saving, I can buy and burn industrial waste in my yard to try to make up for it.
:Cueball: Ah, yeah, carbon onsets.

{{comic discussion}}<noinclude>

3226: Home Solar

2026-03-30T21:52:11Z

WikipedianPolitician: added first bit of summary

{{comic
| number = 3226
| date = March 30, 2026
| title = Home Solar
| image = home_solar_2x.png
| imagesize = 740x258px
| noexpand = true
| titletext = "While I try to do my part to destroy the environment, I try not to focus too much on individual responsibility. By pushing for broad policy changes, we can collectively do far more damage to the biosphere than any of us could on our own."
}}

==Explanation==
{{incomplete|This page was created recently. Don't remove this notice too soon.}}
Black Hat and Cueball are outside Black Hat's house (presumably) discussing the solar panels he has recently installed on the roof. Cueball asks why he has done this, as he claims Black Hat has described himself as anti-renewable. Black Hat responds that, as much as he'd prefer an option that harmed the planet more, solar power is simply the cheapest option and his budget is incapable of supporting anything else.

==Transcript==
{{incomplete transcript|Don't remove this notice too soon.}}
:[Black Hat and Cueball stand next to a house with solar panels on the roof]
:Cueball: Wait, you got solar panels? I thought you were against renewables.
:[Black Hat and Cueball are still discussing]
:Black Hat: Oh, Definitely. I hate the environment and want to harm it as much as possible.
:Black Hat: I'd '''Love''' to have an oil furnace.
:[Zoom on Black Hat]
:Black Hat: But the technology just isn't there and the cost is too high.
:Black Hat: I despise solar, but it makes more financial sense in my situation.
:[Return to previous zoom]
:Black Hat: But with the money I'm saving, I can buy and burn industrial waste in my yard to try to make up for it.
:Cueball: Ah, yeah, carbon onsets.

{{comic discussion}}<noinclude>

3226: Home Solar

2026-03-30T21:49:05Z

WikipedianPolitician: fixed offset

3226: Home Solar

2026-03-30T21:48:14Z

WikipedianPolitician: added line breaks

3226: Home Solar

2026-03-30T21:47:24Z

WikipedianPolitician: Added Transcript

Talk:287: NP-Complete

2026-03-25T00:21:10Z

WikipedianPolitician:

;Unique deciphering requires unique pricetags
Shame this only works in restaurants that price all their appetizers differently. [[User:Davidy22|Davidy22]] ([[User talk:Davidy22|talk]]) 03:18, 13 October 2012 (UTC)
:Not necessarily because the NP-problem allows for any equivocally competing sum certifying how the total can be reached. Shared pricetags as well as a nonpositive would add degrees of freedom and make it impossible to rule out surprise deliveries even through exponential pretesting. Unless the waiter is running into the exponential worst case, the six waiting tables can be attended to immediately upon finding the first feasible combination: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Trivial solution first found
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. [[User:Katya|Katya]] ([[User talk:Katya|talk]]) 02:17, 23 November 2012 (UTC)

;Traveling Salesman Problem
Note: Traveling Salesman Problem ''might'' be mentioned ''also'' because both this problem and the Knapsack problem to be solved belong to set of '''[[wikipedia:NP-complete|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. --[[User:JakubNarebski|JakubNarebski]] ([[User talk:JakubNarebski|talk]]) 16:00, 11 December 2012 (UTC)
:Yes, indeed! I think both meanings are intended to fully get the joke. The <code>TSP:={(n,d,M)∈ℕ×({0…n}²→ℕ)×ℕ|∃c∈{1…n}ⁿ:{1…n}=⋃{cₙ|n∈{1…n}}∧∑{d(cₙ,c₍ₙ₊₁₎)|n∈{0…n}}<M}</code> can both help to timely attend to the six waiting tables and to reduce the <code>ORDERSUM:={(a,b)∈ℕ*×ℕ|∃c∈ℕ*:∑{cₙaₙ|n∈ℕ}=b}</code> problem to. Plus, the "as fast as possible" pun seems to allude to the again six ridiculous inputs any trained human will rearrange to a near-exact solution quicker than they are entered into a computer who can quickly exhaust this tiny search space for an exact solution: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Trivial solution was not intended
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. [[User:Xrays Knock Charms Down|Xrays Knock Charms Down]] ([[User talk: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 [[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 11:02, 10 March 2014 (UTC)
::Cool reference, thanks! [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)
:::How could Randall have missed that the '''first price''' was a solution, when drawing the strip? I know not everyone can do this kind of math in their head, but when I read the $15.05 and glanced over at the menu, that $2.15 was an even denominator of $15.05 was immediately apparent. I'm pretty sure that it'd be hard for him to miss, even if he actually has to use arabic notation to figure it out, which would take like three seconds. —[[User:Kazvorpal|Kazvorpal]] ([[User talk:Kazvorpal|talk]]) 16:23, 1 November 2019 (UTC)
::::Okay, reading the interview, all I can say is that this is a pitfall of taking longcut coding shortcuts. Speaking as a perl programmer, it'd take longer to write that algorithm than to quickly do at least the basic multiples of the prices in one's head, even if one has to do it through mental arabic notation (I have mental shortcuts I worked out before learning math notation in grade school, or in some cases simply "see" the answer).—[[User:Kazvorpal|Kazvorpal]] ([[User talk:Kazvorpal|talk]]) 16:28, 1 November 2019 (UTC)

;Complex solution found in a second
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.
[[Special:Contributions/84.56.77.11|84.56.77.11]]

Did I find another solution or am I missing something (besides sleep)? I created a spreadsheet of prices and line totals and found a solution after 3 or 4 tries. Two mixed fruit, one mozarella sticks, and one BBQ sandwich. Once I found that, I realized the trival solution. Then saw in the explanation there are only two solutions but they didn't match mine with BBQ. Correct, no? Of course a general solution would be much more satisfying. [[User:ProfDigory|ProfDigory]] ([[User talk:ProfDigory|talk]]) 01:07, 10 July 2024 (UTC)
::BBQ sandwiches are not classified as appetizers, so that solution doesn't meet the criteria. [[Special:Contributions/172.69.130.236|172.69.130.236]] 12:37, 20 May 2025 (UTC)

;Not the knapsack problem
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 {{w|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. --[[User:Quicksilver|Quicksilver]] ([[User talk:Quicksilver|talk]]) 18:34, 22 August 2013 (UTC)
:I did some clean-ups, but the the "In computational complexity theory" still needs a review.--[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 20:19, 22 August 2013 (UTC)
::The Wikipedia article on {{w|Karp's 21 NP-complete problems}} hints that Karp originally defined <code>KNAPSACK:={(a,b)∈ℤ*×ℤ|∃c∈𝔹*:∑{cₙaₙ|n∈ℕ}=b}</code> closer to today's shape of <code>SUBSETSUM:={Z⊂ℤ|∃s⊆Z:∑s=0∧s≠∅}</code> than that of the Unbounded Knapsack Problem <code>UKP:={(v,w,V,W)∈ℤ*×ℤ*×ℤ×ℤ|∃c∈ℕ*:{∑{cₙvₙ|n∈ℕ},∑{cₙwₙ|n∈ℕ}}⊆{V…W}}</code> with the former via <code>Z:={b,-a₁…-aₙ,-2a₁…-2aₙ,…}</code> and the latter via <code>(v,w,V,W):=(a,a,b,b)</code> coming close enough to what we really need here, namely <code>ORDERSUM:={(a,b)∈ℕ*×ℕ|∃c∈ℕ*:∑{cₙaₙ|n∈ℕ}=b}</code>. So Randall did hit it bull's eye after all! [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;NP Food
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 [http://www.np-food.com NP Food]. Worth including above? -- [[User:Copito|Copito]] ([[User talk:Copito|talk]]) 20:43, 8 November 2013 (UTC)

That site doesn't work for me. —[[User:TobyBartels|TobyBartels]] ([[User talk:TobyBartels|talk]]) 10:07, 19 November 2013 (UTC)

:I do get more than nothing: a redirect to the HTTPS port whose certificate is signed only to .np-food.com without WWW and whose HTML and PNG and JS suggest that either solutions for San Francisco, Austin, Saint Louis, Miami, and New York menues have been memoized and that you may order by entering your credit card credentials or that only fools wait for a computer to calculate an NP-hard problem on too large a search space. [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Exhaustive Solution
[[user:Roman Czyborra|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. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 19:11, 14 May 2014 (UTC)

Yes, I did.
Because I did think it was helpful.
Not just because an (effective if not efficient) general solution earns you a 50% on $15.05 tip.

Moreover to demonstrate that and how a complete search finds those two solutions.

And that the search tree can branch exponentially with each additional menu item.
Or with additional dollar bills to be spent.
Notwithstanding that any constructive proof of NP=P would let us replace this
straightforward bad NP-implementation with an equivalent better P-implementation.
Before Donald Knuth coined the name NP-Complete, the class was suggested to be named
'''PET''' for the (Probably(while NP?P)|(Proven(if NP>P)|Previously(if NP=P))) Exponential Time pet problems.

What is so confusing about the calculation?
The whole cent amounts instead of dollar floats?
My naming of variables?
Should <code>totaling</code> be renamed to <code>solutions</code> or <code>orders</code>?
Or <code>menu</code> to <code>menu_items</code> or <code>appetizers</code> or <code>pricetags</code>?
<code lang=haskell>
type Cents = Int
orders :: [Cents] -> Cents -> [ [Cents] ]
orders menu total =
total == 0 | [ [] ]
menu == [] | []
total < 0 | []
total > 0 | orders (tail menu) total ++ map (
head menu :) orders menu (total - head menu)

orders [215,275,335,355,420,580] 1505
== [[215,355,355,580],[215,215,215,215,215,215,215]]

calls menu total = if null menu || total < 1
then 1 else 1 + calls (tail menu) total +
calls menu (total - head menu)
calls [] 1505
== 1
calls [580] 1505
== 7
calls [420,580] 1505
== 25
calls [355,420,580] 1505
== 73
calls [335,355,420,580] 1505
== 181
calls [275,335,355,420,580] 1505
== 437
calls [215,275,335,355,420,580] 1505
== 1153
</code>
Or is it the committee language Haskell that is causing problems?
What other well-defined language would you formulate a general solution in?

:If anyone wants to implement this in Python: calculate in cents, use fixed-point arithmetic, or check if the absolute difference is under some tolerance, otherwise the 7 mixed fruit solution is missed. <tt>print(7 * 2.15 == 15.05)</tt> gives <tt>False</tt>.

Discussing all of this is helpful.
Leaving a "Thus" result without its afferent reasoning (and its deleted heading) is not, is it?
Cheers: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

:Please let's keep this code at the discussion page. No common reader would understand; the explain is not only for programmers. I'm a programmer, knowing many languages like BASIC, Pascal, C, C++, Java, Bash, Perl... also HTML, JavaScript... RPG, Databases and SQL... and much more. And if you like to buy an IBM Power 8 I can tell you the proper configuration for your needs.
:But these details are not helpful to explain the comic. There is math that has to be explained. Findings on program codes do even not belong to a trivia section. Nevertheless it seems I have to take a closer look on Haskell, which is not used by many people. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 21:22, 15 May 2014 (UTC)

A 50% tip on a $ 15.05 order is not possible, is it? --[[Special:Contributions/108.162.231.186|108.162.231.186]] 21:08, 1 November 2014 (UTC)

If I were the waiter my response would, at best, be "I'll come back when you're ready to order". At worse it would probably involve burns. -Pennpenn [[Special:Contributions/108.162.250.162|108.162.250.162]] 04:27, 7 October 2015 (UTC)

---Easiest response: "Excellent, Sir. I'll raise the price of the french fries to $15.05 - [[User:Ruffy314|Ruffy314]] ([[User talk:Ruffy314|talk]]) 18:19, 21 November 2015 (UTC)

If we assume that "general solutions" implies that it's a polynomial-time solution, is a 50% tip $7.55, $500 000, or $500 007.55? [[User:Hppavilion1|Hppavilion1]] ([[User talk:Hppavilion1|talk]]) 02:32, 16 September 2017 (UTC)

;A similar situation in real life
Nobody would do that in real life, right? But look at http://www.numberphile.com/videos/43_nuggets.html . A guy orders 43 chicken nuggets, which come in boxes of 6, 9 and 20. It is also a Knapsack problem in a menu order. But in that case there is no solution.
:I tried solving what you described without of clicking the link (still didn't) and before reading the last sentence, and this one is very obvious and quick to find not solvable. As 43 is abviously not dividable by 3 (as one can see at first glance and which would be required to use only 9-boxes and 6-boxes) we need at least one 20-box. Leaving 23 nuggets. That's still not dividable by 3 so there is another 20-box, leaving us at 3 nuggets. Other approach sees that at first we need a package of 9, to get to an even number, and then 9-boxes can only be choosen in pairs at 18-boxes which is no benefit to 6-boxes, so it is only 6 and 20 left. 34 is not dividable by 3 and/or 6. So again subtracting 20 makes it 14, which is obvious to be unsolvable by using only 6-boxes. So "your" problem is quite more trivial. BTW: please sign your comments. --[[User:Lupo|Lupo]] ([[User talk:Lupo|talk]]) 10:42, 24 June 2019 (UTC)

TSP is NP-hard, not NP-complete [[User:Tembrel|Tembrel]] ([[User talk:Tembrel|talk]]) 00:19, 14 November 2019 (UTC)

If you guys like the knapsack problem and simplified stuff, then I've got the game mod for you! https://steamcommunity.com/sharedfiles/filedetails/?id=1844662069 along with https://ktane.timwi.de/HTML/Simon%20Selects.html

(I also tried solving this like I would that mod, but then I realized that this problem is not that.) [[Special:Contributions/172.69.34.24|172.69.34.24]] 03:05, 18 July 2020 (UTC)

;On general solutions
The explanation seems to assume that general solutions must be in polynomial time, but the comic does not mention that. It seemed to me that finding a non-polynomial general solution (which exist, obviously, with one even described in the explanation) *still* gets a 50% tip, which also means the 50% tip is a lot more reasonable now. While mentioning that no polynomial GS exists is probably still a good idea, it seems to me that the explanation should not assume one is neccessary for the tip. [[Special:Contributions/172.68.238.109|172.68.238.109]] 00:59, 24 October 2022 (UTC)

;Should this be in the Multiple Cueballs category?

The guy ordering, plus his companion and the waiter are all cueballs, unless I've misunderstood. [[User:WikipedianPolitician|WikipedianPolitician]] ([[User talk:WikipedianPolitician|talk]]) 23:45, 24 March 2026 (UTC)
:Probably should be, yeah... Easy enough to add it. [[Special:Contributions/81.179.199.253|81.179.199.253]] 00:16, 25 March 2026 (UTC)
::Done! :) [[User:WikipedianPolitician|WikipedianPolitician]] ([[User talk:WikipedianPolitician|talk]]) 00:21, 25 March 2026 (UTC)

287: NP-Complete

2026-03-25T00:19:27Z

WikipedianPolitician: added category!

{{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 [[:Category:My Hobby|My Hobby series]]. [[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, unless the order is very large.

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 [https://web.archive.org/web/20150817221154/http://www.maa.org/press/periodicals/math-horizons/the-mathematics-behind-xkcd-a-conversation-with-randall-munroe-0 an interview] with the Mathematical Association of America, Randall said that the trivial answer to this problem was a mistake. <br/> Randall explains in ''[[xkcd: volume 0]]'' that this was due to him using a Perl script with a bug ("You can't compare IEEE floats for equality").

{{comic discussion}}
[[Category:Comics featuring Cueball]]
[[Category:My Hobby]]
[[Category:Comics with color]]
[[Category:Math]]
[[Category:Programming]]
[[Category:Comics with a Spanish translation]]
[[Category:Multiple Cueballs]]

Talk:3223: Inflation Timeline

2026-03-25T00:17:31Z

WikipedianPolitician: comment, interesting context

What about the regular/sexy thing? {{unsigned|2a02:26f7:e344:4000:c000::f}}
: https://en.wikipedia.org/wiki/Body_inflation [[Special:Contributions/155.33.87.241|155.33.87.241]] 19:14, 23 March 2026 (UTC)
:: I would say this is an application of the "today's lucky 10,000" concept, but this probably doesn't qualify as a thing that everyone knows by the time they're an adult so the number is probably lower. But I hope this experience of learning something new is still as fun as Coke and Mentos! [[User:Dextrous Fred|Dextrous Fred]] ([[User talk:Dextrous Fred|talk]]) 19:47, 23 March 2026 (UTC)
:::Not so sure closing this gap in knowledge would really count as "lucky", but each to their own. [[Special:Contributions/204.77.3.72|204.77.3.72]] 00:07, 24 March 2026 (UTC)
::::definitely not a sentence i expected to read on xkcd. [[user:lett‪herebedarklight|raeb]] 05:33, 24 March 2026 (UTC)
::Since economic inflation is money becoming more worthless and therefore de-facto vanishing, it would be better represented by ''body deflation''. That is - character becoming increasingly more gaunt and skinny, until only pile of bones remain (or if cartoonish, until he becomes thinner than fishing line and collapses into a point). Dunno what sort of weirdo would use images of starving people (e.g. victims of nazi death camps) ''for sexual gratification''. --[[User:User 8496351|User 8496351]] ([[User talk:User 8496351|talk]]) 07:56, 24 March 2026 (UTC)
:::Economic inflation is "more units of money needed for the same product/service", so entirely in line with "a need for more apparent body mass/volume of the same person" (e.g. BBLs, etc). At least as I understand both processes, which I may not entirely. [[Special:Contributions/82.132.237.186|82.132.237.186]] 11:47, 24 March 2026 (UTC)
:: Well, I've obviously led a sheltered the last seventy years as I've never heard of body inflation.--[[Special:Contributions/2A00:23CC:D248:8901:D030:98E4:E22B:D2EF|2A00:23CC:D248:8901:D030:98E4:E22B:D2EF]] 08:56, 24 March 2026 (UTC)
:: New to me too. But further proof of Rule 34 :-) [[Special:Contributions/2A12:F43:143E:0:C172:A03D:12FE:51AA|2A12:F43:143E:0:C172:A03D:12FE:51AA]] 11:36, 24 March 2026 (UTC)dww-uk
The X axis is weird. The labeled ticks are logarithmic, but the unlabeled ticks are linear, and there are only 8 of them.[[User:Jp5424|Jp5424]] ([[User talk:Jp5424|talk]]) 18:18, 24 March 2026 (UTC)
:The X axis most likely has a logarithmic base interval of 10/8, going from 10^-40 to 10^-38.75, 10^-37.5, etc. [[Special:Contributions/2001:1C02:1A9D:9700:2416:3C14:B648:3FD0|2001:1C02:1A9D:9700:2416:3C14:B648:3FD0]] 19:12, 24 March 2026 (UTC)

I don't find the current explanation of sexy coexisting with regular convincing. I think there is something missing. --[[Special:Contributions/80.187.75.215|80.187.75.215]] 22:03, 24 March 2026 (UTC)
:[[174: That's What SHE Said]]... [[Special:Contributions/81.179.199.253|81.179.199.253]] 00:11, 25 March 2026 (UTC)

Fun fact: while debasement of the coinage, rulers melting down coins and resmithing them at lower metal value, has been around for a long time, inflation is pretty new. Inflation calculators for the british pound show pretty flat value until the 1900s despite lots of economic crisis in the 800 years they've been measuring. The US used to use the gold standard, it was only later (gold dollar and dollar standards) that inflation has really been a thing in the US. Thus the 'regular' period of inflation is probably pretty short, about the last 100 years. [[User:WikipedianPolitician|WikipedianPolitician]] ([[User talk:WikipedianPolitician|talk]]) 00:17, 25 March 2026 (UTC)

Talk:287: NP-Complete

2026-03-24T23:46:56Z

WikipedianPolitician: /* Should this be in the Multiple Cueballs category? */ sorry I forgot about edit summaries/this has just been me fixing the heading format

;Unique deciphering requires unique pricetags
Shame this only works in restaurants that price all their appetizers differently. [[User:Davidy22|Davidy22]] ([[User talk:Davidy22|talk]]) 03:18, 13 October 2012 (UTC)
:Not necessarily because the NP-problem allows for any equivocally competing sum certifying how the total can be reached. Shared pricetags as well as a nonpositive would add degrees of freedom and make it impossible to rule out surprise deliveries even through exponential pretesting. Unless the waiter is running into the exponential worst case, the six waiting tables can be attended to immediately upon finding the first feasible combination: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Trivial solution first found
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. [[User:Katya|Katya]] ([[User talk:Katya|talk]]) 02:17, 23 November 2012 (UTC)

;Traveling Salesman Problem
Note: Traveling Salesman Problem ''might'' be mentioned ''also'' because both this problem and the Knapsack problem to be solved belong to set of '''[[wikipedia:NP-complete|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. --[[User:JakubNarebski|JakubNarebski]] ([[User talk:JakubNarebski|talk]]) 16:00, 11 December 2012 (UTC)
:Yes, indeed! I think both meanings are intended to fully get the joke. The <code>TSP:={(n,d,M)∈ℕ×({0…n}²→ℕ)×ℕ|∃c∈{1…n}ⁿ:{1…n}=⋃{cₙ|n∈{1…n}}∧∑{d(cₙ,c₍ₙ₊₁₎)|n∈{0…n}}<M}</code> can both help to timely attend to the six waiting tables and to reduce the <code>ORDERSUM:={(a,b)∈ℕ*×ℕ|∃c∈ℕ*:∑{cₙaₙ|n∈ℕ}=b}</code> problem to. Plus, the "as fast as possible" pun seems to allude to the again six ridiculous inputs any trained human will rearrange to a near-exact solution quicker than they are entered into a computer who can quickly exhaust this tiny search space for an exact solution: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Trivial solution was not intended
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. [[User:Xrays Knock Charms Down|Xrays Knock Charms Down]] ([[User talk: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 [[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 11:02, 10 March 2014 (UTC)
::Cool reference, thanks! [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)
:::How could Randall have missed that the '''first price''' was a solution, when drawing the strip? I know not everyone can do this kind of math in their head, but when I read the $15.05 and glanced over at the menu, that $2.15 was an even denominator of $15.05 was immediately apparent. I'm pretty sure that it'd be hard for him to miss, even if he actually has to use arabic notation to figure it out, which would take like three seconds. —[[User:Kazvorpal|Kazvorpal]] ([[User talk:Kazvorpal|talk]]) 16:23, 1 November 2019 (UTC)
::::Okay, reading the interview, all I can say is that this is a pitfall of taking longcut coding shortcuts. Speaking as a perl programmer, it'd take longer to write that algorithm than to quickly do at least the basic multiples of the prices in one's head, even if one has to do it through mental arabic notation (I have mental shortcuts I worked out before learning math notation in grade school, or in some cases simply "see" the answer).—[[User:Kazvorpal|Kazvorpal]] ([[User talk:Kazvorpal|talk]]) 16:28, 1 November 2019 (UTC)

;Complex solution found in a second
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.
[[Special:Contributions/84.56.77.11|84.56.77.11]]

Did I find another solution or am I missing something (besides sleep)? I created a spreadsheet of prices and line totals and found a solution after 3 or 4 tries. Two mixed fruit, one mozarella sticks, and one BBQ sandwich. Once I found that, I realized the trival solution. Then saw in the explanation there are only two solutions but they didn't match mine with BBQ. Correct, no? Of course a general solution would be much more satisfying. [[User:ProfDigory|ProfDigory]] ([[User talk:ProfDigory|talk]]) 01:07, 10 July 2024 (UTC)
::BBQ sandwiches are not classified as appetizers, so that solution doesn't meet the criteria. [[Special:Contributions/172.69.130.236|172.69.130.236]] 12:37, 20 May 2025 (UTC)

;Not the knapsack problem
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 {{w|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. --[[User:Quicksilver|Quicksilver]] ([[User talk:Quicksilver|talk]]) 18:34, 22 August 2013 (UTC)
:I did some clean-ups, but the the "In computational complexity theory" still needs a review.--[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 20:19, 22 August 2013 (UTC)
::The Wikipedia article on {{w|Karp's 21 NP-complete problems}} hints that Karp originally defined <code>KNAPSACK:={(a,b)∈ℤ*×ℤ|∃c∈𝔹*:∑{cₙaₙ|n∈ℕ}=b}</code> closer to today's shape of <code>SUBSETSUM:={Z⊂ℤ|∃s⊆Z:∑s=0∧s≠∅}</code> than that of the Unbounded Knapsack Problem <code>UKP:={(v,w,V,W)∈ℤ*×ℤ*×ℤ×ℤ|∃c∈ℕ*:{∑{cₙvₙ|n∈ℕ},∑{cₙwₙ|n∈ℕ}}⊆{V…W}}</code> with the former via <code>Z:={b,-a₁…-aₙ,-2a₁…-2aₙ,…}</code> and the latter via <code>(v,w,V,W):=(a,a,b,b)</code> coming close enough to what we really need here, namely <code>ORDERSUM:={(a,b)∈ℕ*×ℕ|∃c∈ℕ*:∑{cₙaₙ|n∈ℕ}=b}</code>. So Randall did hit it bull's eye after all! [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;NP Food
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 [http://www.np-food.com NP Food]. Worth including above? -- [[User:Copito|Copito]] ([[User talk:Copito|talk]]) 20:43, 8 November 2013 (UTC)

That site doesn't work for me. —[[User:TobyBartels|TobyBartels]] ([[User talk:TobyBartels|talk]]) 10:07, 19 November 2013 (UTC)

:I do get more than nothing: a redirect to the HTTPS port whose certificate is signed only to .np-food.com without WWW and whose HTML and PNG and JS suggest that either solutions for San Francisco, Austin, Saint Louis, Miami, and New York menues have been memoized and that you may order by entering your credit card credentials or that only fools wait for a computer to calculate an NP-hard problem on too large a search space. [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Exhaustive Solution
[[user:Roman Czyborra|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. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 19:11, 14 May 2014 (UTC)

Yes, I did.
Because I did think it was helpful.
Not just because an (effective if not efficient) general solution earns you a 50% on $15.05 tip.

Moreover to demonstrate that and how a complete search finds those two solutions.

And that the search tree can branch exponentially with each additional menu item.
Or with additional dollar bills to be spent.
Notwithstanding that any constructive proof of NP=P would let us replace this
straightforward bad NP-implementation with an equivalent better P-implementation.
Before Donald Knuth coined the name NP-Complete, the class was suggested to be named
'''PET''' for the (Probably(while NP?P)|(Proven(if NP>P)|Previously(if NP=P))) Exponential Time pet problems.

What is so confusing about the calculation?
The whole cent amounts instead of dollar floats?
My naming of variables?
Should <code>totaling</code> be renamed to <code>solutions</code> or <code>orders</code>?
Or <code>menu</code> to <code>menu_items</code> or <code>appetizers</code> or <code>pricetags</code>?
<code lang=haskell>
type Cents = Int
orders :: [Cents] -> Cents -> [ [Cents] ]
orders menu total =
total == 0 | [ [] ]
menu == [] | []
total < 0 | []
total > 0 | orders (tail menu) total ++ map (
head menu :) orders menu (total - head menu)

orders [215,275,335,355,420,580] 1505
== [[215,355,355,580],[215,215,215,215,215,215,215]]

calls menu total = if null menu || total < 1
then 1 else 1 + calls (tail menu) total +
calls menu (total - head menu)
calls [] 1505
== 1
calls [580] 1505
== 7
calls [420,580] 1505
== 25
calls [355,420,580] 1505
== 73
calls [335,355,420,580] 1505
== 181
calls [275,335,355,420,580] 1505
== 437
calls [215,275,335,355,420,580] 1505
== 1153
</code>
Or is it the committee language Haskell that is causing problems?
What other well-defined language would you formulate a general solution in?

:If anyone wants to implement this in Python: calculate in cents, use fixed-point arithmetic, or check if the absolute difference is under some tolerance, otherwise the 7 mixed fruit solution is missed. <tt>print(7 * 2.15 == 15.05)</tt> gives <tt>False</tt>.

Discussing all of this is helpful.
Leaving a "Thus" result without its afferent reasoning (and its deleted heading) is not, is it?
Cheers: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

:Please let's keep this code at the discussion page. No common reader would understand; the explain is not only for programmers. I'm a programmer, knowing many languages like BASIC, Pascal, C, C++, Java, Bash, Perl... also HTML, JavaScript... RPG, Databases and SQL... and much more. And if you like to buy an IBM Power 8 I can tell you the proper configuration for your needs.
:But these details are not helpful to explain the comic. There is math that has to be explained. Findings on program codes do even not belong to a trivia section. Nevertheless it seems I have to take a closer look on Haskell, which is not used by many people. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 21:22, 15 May 2014 (UTC)

A 50% tip on a $ 15.05 order is not possible, is it? --[[Special:Contributions/108.162.231.186|108.162.231.186]] 21:08, 1 November 2014 (UTC)

If I were the waiter my response would, at best, be "I'll come back when you're ready to order". At worse it would probably involve burns. -Pennpenn [[Special:Contributions/108.162.250.162|108.162.250.162]] 04:27, 7 October 2015 (UTC)

---Easiest response: "Excellent, Sir. I'll raise the price of the french fries to $15.05 - [[User:Ruffy314|Ruffy314]] ([[User talk:Ruffy314|talk]]) 18:19, 21 November 2015 (UTC)

If we assume that "general solutions" implies that it's a polynomial-time solution, is a 50% tip $7.55, $500 000, or $500 007.55? [[User:Hppavilion1|Hppavilion1]] ([[User talk:Hppavilion1|talk]]) 02:32, 16 September 2017 (UTC)

;A similar situation in real life
Nobody would do that in real life, right? But look at http://www.numberphile.com/videos/43_nuggets.html . A guy orders 43 chicken nuggets, which come in boxes of 6, 9 and 20. It is also a Knapsack problem in a menu order. But in that case there is no solution.
:I tried solving what you described without of clicking the link (still didn't) and before reading the last sentence, and this one is very obvious and quick to find not solvable. As 43 is abviously not dividable by 3 (as one can see at first glance and which would be required to use only 9-boxes and 6-boxes) we need at least one 20-box. Leaving 23 nuggets. That's still not dividable by 3 so there is another 20-box, leaving us at 3 nuggets. Other approach sees that at first we need a package of 9, to get to an even number, and then 9-boxes can only be choosen in pairs at 18-boxes which is no benefit to 6-boxes, so it is only 6 and 20 left. 34 is not dividable by 3 and/or 6. So again subtracting 20 makes it 14, which is obvious to be unsolvable by using only 6-boxes. So "your" problem is quite more trivial. BTW: please sign your comments. --[[User:Lupo|Lupo]] ([[User talk:Lupo|talk]]) 10:42, 24 June 2019 (UTC)

TSP is NP-hard, not NP-complete [[User:Tembrel|Tembrel]] ([[User talk:Tembrel|talk]]) 00:19, 14 November 2019 (UTC)

If you guys like the knapsack problem and simplified stuff, then I've got the game mod for you! https://steamcommunity.com/sharedfiles/filedetails/?id=1844662069 along with https://ktane.timwi.de/HTML/Simon%20Selects.html

(I also tried solving this like I would that mod, but then I realized that this problem is not that.) [[Special:Contributions/172.69.34.24|172.69.34.24]] 03:05, 18 July 2020 (UTC)

;On general solutions
The explanation seems to assume that general solutions must be in polynomial time, but the comic does not mention that. It seemed to me that finding a non-polynomial general solution (which exist, obviously, with one even described in the explanation) *still* gets a 50% tip, which also means the 50% tip is a lot more reasonable now. While mentioning that no polynomial GS exists is probably still a good idea, it seems to me that the explanation should not assume one is neccessary for the tip. [[Special:Contributions/172.68.238.109|172.68.238.109]] 00:59, 24 October 2022 (UTC)

==== Should this be in the Multiple Cueballs category? ====

The guy ordering, plus his companion and the waiter are all cueballs, unless I've misunderstood. [[User:WikipedianPolitician|WikipedianPolitician]] ([[User talk:WikipedianPolitician|talk]]) 23:45, 24 March 2026 (UTC)

Talk:287: NP-Complete

2026-03-24T23:45:58Z

WikipedianPolitician: /* Should this be in the Multiple Cueballs category? */

;Unique deciphering requires unique pricetags
Shame this only works in restaurants that price all their appetizers differently. [[User:Davidy22|Davidy22]] ([[User talk:Davidy22|talk]]) 03:18, 13 October 2012 (UTC)
:Not necessarily because the NP-problem allows for any equivocally competing sum certifying how the total can be reached. Shared pricetags as well as a nonpositive would add degrees of freedom and make it impossible to rule out surprise deliveries even through exponential pretesting. Unless the waiter is running into the exponential worst case, the six waiting tables can be attended to immediately upon finding the first feasible combination: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Trivial solution first found
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. [[User:Katya|Katya]] ([[User talk:Katya|talk]]) 02:17, 23 November 2012 (UTC)

;Traveling Salesman Problem
Note: Traveling Salesman Problem ''might'' be mentioned ''also'' because both this problem and the Knapsack problem to be solved belong to set of '''[[wikipedia:NP-complete|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. --[[User:JakubNarebski|JakubNarebski]] ([[User talk:JakubNarebski|talk]]) 16:00, 11 December 2012 (UTC)
:Yes, indeed! I think both meanings are intended to fully get the joke. The <code>TSP:={(n,d,M)∈ℕ×({0…n}²→ℕ)×ℕ|∃c∈{1…n}ⁿ:{1…n}=⋃{cₙ|n∈{1…n}}∧∑{d(cₙ,c₍ₙ₊₁₎)|n∈{0…n}}<M}</code> can both help to timely attend to the six waiting tables and to reduce the <code>ORDERSUM:={(a,b)∈ℕ*×ℕ|∃c∈ℕ*:∑{cₙaₙ|n∈ℕ}=b}</code> problem to. Plus, the "as fast as possible" pun seems to allude to the again six ridiculous inputs any trained human will rearrange to a near-exact solution quicker than they are entered into a computer who can quickly exhaust this tiny search space for an exact solution: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Trivial solution was not intended
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. [[User:Xrays Knock Charms Down|Xrays Knock Charms Down]] ([[User talk: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 [[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 11:02, 10 March 2014 (UTC)
::Cool reference, thanks! [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)
:::How could Randall have missed that the '''first price''' was a solution, when drawing the strip? I know not everyone can do this kind of math in their head, but when I read the $15.05 and glanced over at the menu, that $2.15 was an even denominator of $15.05 was immediately apparent. I'm pretty sure that it'd be hard for him to miss, even if he actually has to use arabic notation to figure it out, which would take like three seconds. —[[User:Kazvorpal|Kazvorpal]] ([[User talk:Kazvorpal|talk]]) 16:23, 1 November 2019 (UTC)
::::Okay, reading the interview, all I can say is that this is a pitfall of taking longcut coding shortcuts. Speaking as a perl programmer, it'd take longer to write that algorithm than to quickly do at least the basic multiples of the prices in one's head, even if one has to do it through mental arabic notation (I have mental shortcuts I worked out before learning math notation in grade school, or in some cases simply "see" the answer).—[[User:Kazvorpal|Kazvorpal]] ([[User talk:Kazvorpal|talk]]) 16:28, 1 November 2019 (UTC)

;Complex solution found in a second
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.
[[Special:Contributions/84.56.77.11|84.56.77.11]]

Did I find another solution or am I missing something (besides sleep)? I created a spreadsheet of prices and line totals and found a solution after 3 or 4 tries. Two mixed fruit, one mozarella sticks, and one BBQ sandwich. Once I found that, I realized the trival solution. Then saw in the explanation there are only two solutions but they didn't match mine with BBQ. Correct, no? Of course a general solution would be much more satisfying. [[User:ProfDigory|ProfDigory]] ([[User talk:ProfDigory|talk]]) 01:07, 10 July 2024 (UTC)
::BBQ sandwiches are not classified as appetizers, so that solution doesn't meet the criteria. [[Special:Contributions/172.69.130.236|172.69.130.236]] 12:37, 20 May 2025 (UTC)

;Not the knapsack problem
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 {{w|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. --[[User:Quicksilver|Quicksilver]] ([[User talk:Quicksilver|talk]]) 18:34, 22 August 2013 (UTC)
:I did some clean-ups, but the the "In computational complexity theory" still needs a review.--[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 20:19, 22 August 2013 (UTC)
::The Wikipedia article on {{w|Karp's 21 NP-complete problems}} hints that Karp originally defined <code>KNAPSACK:={(a,b)∈ℤ*×ℤ|∃c∈𝔹*:∑{cₙaₙ|n∈ℕ}=b}</code> closer to today's shape of <code>SUBSETSUM:={Z⊂ℤ|∃s⊆Z:∑s=0∧s≠∅}</code> than that of the Unbounded Knapsack Problem <code>UKP:={(v,w,V,W)∈ℤ*×ℤ*×ℤ×ℤ|∃c∈ℕ*:{∑{cₙvₙ|n∈ℕ},∑{cₙwₙ|n∈ℕ}}⊆{V…W}}</code> with the former via <code>Z:={b,-a₁…-aₙ,-2a₁…-2aₙ,…}</code> and the latter via <code>(v,w,V,W):=(a,a,b,b)</code> coming close enough to what we really need here, namely <code>ORDERSUM:={(a,b)∈ℕ*×ℕ|∃c∈ℕ*:∑{cₙaₙ|n∈ℕ}=b}</code>. So Randall did hit it bull's eye after all! [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;NP Food
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 [http://www.np-food.com NP Food]. Worth including above? -- [[User:Copito|Copito]] ([[User talk:Copito|talk]]) 20:43, 8 November 2013 (UTC)

That site doesn't work for me. —[[User:TobyBartels|TobyBartels]] ([[User talk:TobyBartels|talk]]) 10:07, 19 November 2013 (UTC)

:I do get more than nothing: a redirect to the HTTPS port whose certificate is signed only to .np-food.com without WWW and whose HTML and PNG and JS suggest that either solutions for San Francisco, Austin, Saint Louis, Miami, and New York menues have been memoized and that you may order by entering your credit card credentials or that only fools wait for a computer to calculate an NP-hard problem on too large a search space. [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Exhaustive Solution
[[user:Roman Czyborra|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. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 19:11, 14 May 2014 (UTC)

Yes, I did.
Because I did think it was helpful.
Not just because an (effective if not efficient) general solution earns you a 50% on $15.05 tip.

Moreover to demonstrate that and how a complete search finds those two solutions.

And that the search tree can branch exponentially with each additional menu item.
Or with additional dollar bills to be spent.
Notwithstanding that any constructive proof of NP=P would let us replace this
straightforward bad NP-implementation with an equivalent better P-implementation.
Before Donald Knuth coined the name NP-Complete, the class was suggested to be named
'''PET''' for the (Probably(while NP?P)|(Proven(if NP>P)|Previously(if NP=P))) Exponential Time pet problems.

What is so confusing about the calculation?
The whole cent amounts instead of dollar floats?
My naming of variables?
Should <code>totaling</code> be renamed to <code>solutions</code> or <code>orders</code>?
Or <code>menu</code> to <code>menu_items</code> or <code>appetizers</code> or <code>pricetags</code>?
<code lang=haskell>
type Cents = Int
orders :: [Cents] -> Cents -> [ [Cents] ]
orders menu total =
total == 0 | [ [] ]
menu == [] | []
total < 0 | []
total > 0 | orders (tail menu) total ++ map (
head menu :) orders menu (total - head menu)

orders [215,275,335,355,420,580] 1505
== [[215,355,355,580],[215,215,215,215,215,215,215]]

calls menu total = if null menu || total < 1
then 1 else 1 + calls (tail menu) total +
calls menu (total - head menu)
calls [] 1505
== 1
calls [580] 1505
== 7
calls [420,580] 1505
== 25
calls [355,420,580] 1505
== 73
calls [335,355,420,580] 1505
== 181
calls [275,335,355,420,580] 1505
== 437
calls [215,275,335,355,420,580] 1505
== 1153
</code>
Or is it the committee language Haskell that is causing problems?
What other well-defined language would you formulate a general solution in?

:If anyone wants to implement this in Python: calculate in cents, use fixed-point arithmetic, or check if the absolute difference is under some tolerance, otherwise the 7 mixed fruit solution is missed. <tt>print(7 * 2.15 == 15.05)</tt> gives <tt>False</tt>.

Discussing all of this is helpful.
Leaving a "Thus" result without its afferent reasoning (and its deleted heading) is not, is it?
Cheers: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

:Please let's keep this code at the discussion page. No common reader would understand; the explain is not only for programmers. I'm a programmer, knowing many languages like BASIC, Pascal, C, C++, Java, Bash, Perl... also HTML, JavaScript... RPG, Databases and SQL... and much more. And if you like to buy an IBM Power 8 I can tell you the proper configuration for your needs.
:But these details are not helpful to explain the comic. There is math that has to be explained. Findings on program codes do even not belong to a trivia section. Nevertheless it seems I have to take a closer look on Haskell, which is not used by many people. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 21:22, 15 May 2014 (UTC)

A 50% tip on a $ 15.05 order is not possible, is it? --[[Special:Contributions/108.162.231.186|108.162.231.186]] 21:08, 1 November 2014 (UTC)

If I were the waiter my response would, at best, be "I'll come back when you're ready to order". At worse it would probably involve burns. -Pennpenn [[Special:Contributions/108.162.250.162|108.162.250.162]] 04:27, 7 October 2015 (UTC)

---Easiest response: "Excellent, Sir. I'll raise the price of the french fries to $15.05 - [[User:Ruffy314|Ruffy314]] ([[User talk:Ruffy314|talk]]) 18:19, 21 November 2015 (UTC)

If we assume that "general solutions" implies that it's a polynomial-time solution, is a 50% tip $7.55, $500 000, or $500 007.55? [[User:Hppavilion1|Hppavilion1]] ([[User talk:Hppavilion1|talk]]) 02:32, 16 September 2017 (UTC)

;A similar situation in real life
Nobody would do that in real life, right? But look at http://www.numberphile.com/videos/43_nuggets.html . A guy orders 43 chicken nuggets, which come in boxes of 6, 9 and 20. It is also a Knapsack problem in a menu order. But in that case there is no solution.
:I tried solving what you described without of clicking the link (still didn't) and before reading the last sentence, and this one is very obvious and quick to find not solvable. As 43 is abviously not dividable by 3 (as one can see at first glance and which would be required to use only 9-boxes and 6-boxes) we need at least one 20-box. Leaving 23 nuggets. That's still not dividable by 3 so there is another 20-box, leaving us at 3 nuggets. Other approach sees that at first we need a package of 9, to get to an even number, and then 9-boxes can only be choosen in pairs at 18-boxes which is no benefit to 6-boxes, so it is only 6 and 20 left. 34 is not dividable by 3 and/or 6. So again subtracting 20 makes it 14, which is obvious to be unsolvable by using only 6-boxes. So "your" problem is quite more trivial. BTW: please sign your comments. --[[User:Lupo|Lupo]] ([[User talk:Lupo|talk]]) 10:42, 24 June 2019 (UTC)

TSP is NP-hard, not NP-complete [[User:Tembrel|Tembrel]] ([[User talk:Tembrel|talk]]) 00:19, 14 November 2019 (UTC)

If you guys like the knapsack problem and simplified stuff, then I've got the game mod for you! https://steamcommunity.com/sharedfiles/filedetails/?id=1844662069 along with https://ktane.timwi.de/HTML/Simon%20Selects.html

(I also tried solving this like I would that mod, but then I realized that this problem is not that.) [[Special:Contributions/172.69.34.24|172.69.34.24]] 03:05, 18 July 2020 (UTC)

;On general solutions
The explanation seems to assume that general solutions must be in polynomial time, but the comic does not mention that. It seemed to me that finding a non-polynomial general solution (which exist, obviously, with one even described in the explanation) *still* gets a 50% tip, which also means the 50% tip is a lot more reasonable now. While mentioning that no polynomial GS exists is probably still a good idea, it seems to me that the explanation should not assume one is neccessary for the tip. [[Special:Contributions/172.68.238.109|172.68.238.109]] 00:59, 24 October 2022 (UTC)

=== Should this be in the Multiple Cueballs category? ===

The guy ordering, plus his companion and the waiter are all cueballs, unless I've misunderstood. [[User:WikipedianPolitician|WikipedianPolitician]] ([[User talk:WikipedianPolitician|talk]]) 23:45, 24 March 2026 (UTC)

Talk:287: NP-Complete

2026-03-24T23:45:01Z

WikipedianPolitician: /* Should this be in the Multiple Cueballs category? */ new section

;Unique deciphering requires unique pricetags
Shame this only works in restaurants that price all their appetizers differently. [[User:Davidy22|Davidy22]] ([[User talk:Davidy22|talk]]) 03:18, 13 October 2012 (UTC)
:Not necessarily because the NP-problem allows for any equivocally competing sum certifying how the total can be reached. Shared pricetags as well as a nonpositive would add degrees of freedom and make it impossible to rule out surprise deliveries even through exponential pretesting. Unless the waiter is running into the exponential worst case, the six waiting tables can be attended to immediately upon finding the first feasible combination: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Trivial solution first found
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. [[User:Katya|Katya]] ([[User talk:Katya|talk]]) 02:17, 23 November 2012 (UTC)

;Traveling Salesman Problem
Note: Traveling Salesman Problem ''might'' be mentioned ''also'' because both this problem and the Knapsack problem to be solved belong to set of '''[[wikipedia:NP-complete|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. --[[User:JakubNarebski|JakubNarebski]] ([[User talk:JakubNarebski|talk]]) 16:00, 11 December 2012 (UTC)
:Yes, indeed! I think both meanings are intended to fully get the joke. The <code>TSP:={(n,d,M)∈ℕ×({0…n}²→ℕ)×ℕ|∃c∈{1…n}ⁿ:{1…n}=⋃{cₙ|n∈{1…n}}∧∑{d(cₙ,c₍ₙ₊₁₎)|n∈{0…n}}<M}</code> can both help to timely attend to the six waiting tables and to reduce the <code>ORDERSUM:={(a,b)∈ℕ*×ℕ|∃c∈ℕ*:∑{cₙaₙ|n∈ℕ}=b}</code> problem to. Plus, the "as fast as possible" pun seems to allude to the again six ridiculous inputs any trained human will rearrange to a near-exact solution quicker than they are entered into a computer who can quickly exhaust this tiny search space for an exact solution: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Trivial solution was not intended
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. [[User:Xrays Knock Charms Down|Xrays Knock Charms Down]] ([[User talk: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 [[User:Kynde|Kynde]] ([[User talk:Kynde|talk]]) 11:02, 10 March 2014 (UTC)
::Cool reference, thanks! [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)
:::How could Randall have missed that the '''first price''' was a solution, when drawing the strip? I know not everyone can do this kind of math in their head, but when I read the $15.05 and glanced over at the menu, that $2.15 was an even denominator of $15.05 was immediately apparent. I'm pretty sure that it'd be hard for him to miss, even if he actually has to use arabic notation to figure it out, which would take like three seconds. —[[User:Kazvorpal|Kazvorpal]] ([[User talk:Kazvorpal|talk]]) 16:23, 1 November 2019 (UTC)
::::Okay, reading the interview, all I can say is that this is a pitfall of taking longcut coding shortcuts. Speaking as a perl programmer, it'd take longer to write that algorithm than to quickly do at least the basic multiples of the prices in one's head, even if one has to do it through mental arabic notation (I have mental shortcuts I worked out before learning math notation in grade school, or in some cases simply "see" the answer).—[[User:Kazvorpal|Kazvorpal]] ([[User talk:Kazvorpal|talk]]) 16:28, 1 November 2019 (UTC)

;Complex solution found in a second
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.
[[Special:Contributions/84.56.77.11|84.56.77.11]]

Did I find another solution or am I missing something (besides sleep)? I created a spreadsheet of prices and line totals and found a solution after 3 or 4 tries. Two mixed fruit, one mozarella sticks, and one BBQ sandwich. Once I found that, I realized the trival solution. Then saw in the explanation there are only two solutions but they didn't match mine with BBQ. Correct, no? Of course a general solution would be much more satisfying. [[User:ProfDigory|ProfDigory]] ([[User talk:ProfDigory|talk]]) 01:07, 10 July 2024 (UTC)
::BBQ sandwiches are not classified as appetizers, so that solution doesn't meet the criteria. [[Special:Contributions/172.69.130.236|172.69.130.236]] 12:37, 20 May 2025 (UTC)

;Not the knapsack problem
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 {{w|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. --[[User:Quicksilver|Quicksilver]] ([[User talk:Quicksilver|talk]]) 18:34, 22 August 2013 (UTC)
:I did some clean-ups, but the the "In computational complexity theory" still needs a review.--[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 20:19, 22 August 2013 (UTC)
::The Wikipedia article on {{w|Karp's 21 NP-complete problems}} hints that Karp originally defined <code>KNAPSACK:={(a,b)∈ℤ*×ℤ|∃c∈𝔹*:∑{cₙaₙ|n∈ℕ}=b}</code> closer to today's shape of <code>SUBSETSUM:={Z⊂ℤ|∃s⊆Z:∑s=0∧s≠∅}</code> than that of the Unbounded Knapsack Problem <code>UKP:={(v,w,V,W)∈ℤ*×ℤ*×ℤ×ℤ|∃c∈ℕ*:{∑{cₙvₙ|n∈ℕ},∑{cₙwₙ|n∈ℕ}}⊆{V…W}}</code> with the former via <code>Z:={b,-a₁…-aₙ,-2a₁…-2aₙ,…}</code> and the latter via <code>(v,w,V,W):=(a,a,b,b)</code> coming close enough to what we really need here, namely <code>ORDERSUM:={(a,b)∈ℕ*×ℕ|∃c∈ℕ*:∑{cₙaₙ|n∈ℕ}=b}</code>. So Randall did hit it bull's eye after all! [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;NP Food
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 [http://www.np-food.com NP Food]. Worth including above? -- [[User:Copito|Copito]] ([[User talk:Copito|talk]]) 20:43, 8 November 2013 (UTC)

That site doesn't work for me. —[[User:TobyBartels|TobyBartels]] ([[User talk:TobyBartels|talk]]) 10:07, 19 November 2013 (UTC)

:I do get more than nothing: a redirect to the HTTPS port whose certificate is signed only to .np-food.com without WWW and whose HTML and PNG and JS suggest that either solutions for San Francisco, Austin, Saint Louis, Miami, and New York menues have been memoized and that you may order by entering your credit card credentials or that only fools wait for a computer to calculate an NP-hard problem on too large a search space. [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

;Exhaustive Solution
[[user:Roman Czyborra|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. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 19:11, 14 May 2014 (UTC)

Yes, I did.
Because I did think it was helpful.
Not just because an (effective if not efficient) general solution earns you a 50% on $15.05 tip.

Moreover to demonstrate that and how a complete search finds those two solutions.

And that the search tree can branch exponentially with each additional menu item.
Or with additional dollar bills to be spent.
Notwithstanding that any constructive proof of NP=P would let us replace this
straightforward bad NP-implementation with an equivalent better P-implementation.
Before Donald Knuth coined the name NP-Complete, the class was suggested to be named
'''PET''' for the (Probably(while NP?P)|(Proven(if NP>P)|Previously(if NP=P))) Exponential Time pet problems.

What is so confusing about the calculation?
The whole cent amounts instead of dollar floats?
My naming of variables?
Should <code>totaling</code> be renamed to <code>solutions</code> or <code>orders</code>?
Or <code>menu</code> to <code>menu_items</code> or <code>appetizers</code> or <code>pricetags</code>?
<code lang=haskell>
type Cents = Int
orders :: [Cents] -> Cents -> [ [Cents] ]
orders menu total =
total == 0 | [ [] ]
menu == [] | []
total < 0 | []
total > 0 | orders (tail menu) total ++ map (
head menu :) orders menu (total - head menu)

orders [215,275,335,355,420,580] 1505
== [[215,355,355,580],[215,215,215,215,215,215,215]]

calls menu total = if null menu || total < 1
then 1 else 1 + calls (tail menu) total +
calls menu (total - head menu)
calls [] 1505
== 1
calls [580] 1505
== 7
calls [420,580] 1505
== 25
calls [355,420,580] 1505
== 73
calls [335,355,420,580] 1505
== 181
calls [275,335,355,420,580] 1505
== 437
calls [215,275,335,355,420,580] 1505
== 1153
</code>
Or is it the committee language Haskell that is causing problems?
What other well-defined language would you formulate a general solution in?

:If anyone wants to implement this in Python: calculate in cents, use fixed-point arithmetic, or check if the absolute difference is under some tolerance, otherwise the 7 mixed fruit solution is missed. <tt>print(7 * 2.15 == 15.05)</tt> gives <tt>False</tt>.

Discussing all of this is helpful.
Leaving a "Thus" result without its afferent reasoning (and its deleted heading) is not, is it?
Cheers: [[User:Roman Czyborra|Roman Czyborra]] ([[User talk:Roman Czyborra|talk]]) 15:44, 15 May 2014 (UTC)

:Please let's keep this code at the discussion page. No common reader would understand; the explain is not only for programmers. I'm a programmer, knowing many languages like BASIC, Pascal, C, C++, Java, Bash, Perl... also HTML, JavaScript... RPG, Databases and SQL... and much more. And if you like to buy an IBM Power 8 I can tell you the proper configuration for your needs.
:But these details are not helpful to explain the comic. There is math that has to be explained. Findings on program codes do even not belong to a trivia section. Nevertheless it seems I have to take a closer look on Haskell, which is not used by many people. --[[User:Dgbrt|Dgbrt]] ([[User talk:Dgbrt|talk]]) 21:22, 15 May 2014 (UTC)

A 50% tip on a $ 15.05 order is not possible, is it? --[[Special:Contributions/108.162.231.186|108.162.231.186]] 21:08, 1 November 2014 (UTC)

If I were the waiter my response would, at best, be "I'll come back when you're ready to order". At worse it would probably involve burns. -Pennpenn [[Special:Contributions/108.162.250.162|108.162.250.162]] 04:27, 7 October 2015 (UTC)

---Easiest response: "Excellent, Sir. I'll raise the price of the french fries to $15.05 - [[User:Ruffy314|Ruffy314]] ([[User talk:Ruffy314|talk]]) 18:19, 21 November 2015 (UTC)

If we assume that "general solutions" implies that it's a polynomial-time solution, is a 50% tip $7.55, $500 000, or $500 007.55? [[User:Hppavilion1|Hppavilion1]] ([[User talk:Hppavilion1|talk]]) 02:32, 16 September 2017 (UTC)

;A similar situation in real life
Nobody would do that in real life, right? But look at http://www.numberphile.com/videos/43_nuggets.html . A guy orders 43 chicken nuggets, which come in boxes of 6, 9 and 20. It is also a Knapsack problem in a menu order. But in that case there is no solution.
:I tried solving what you described without of clicking the link (still didn't) and before reading the last sentence, and this one is very obvious and quick to find not solvable. As 43 is abviously not dividable by 3 (as one can see at first glance and which would be required to use only 9-boxes and 6-boxes) we need at least one 20-box. Leaving 23 nuggets. That's still not dividable by 3 so there is another 20-box, leaving us at 3 nuggets. Other approach sees that at first we need a package of 9, to get to an even number, and then 9-boxes can only be choosen in pairs at 18-boxes which is no benefit to 6-boxes, so it is only 6 and 20 left. 34 is not dividable by 3 and/or 6. So again subtracting 20 makes it 14, which is obvious to be unsolvable by using only 6-boxes. So "your" problem is quite more trivial. BTW: please sign your comments. --[[User:Lupo|Lupo]] ([[User talk:Lupo|talk]]) 10:42, 24 June 2019 (UTC)

TSP is NP-hard, not NP-complete [[User:Tembrel|Tembrel]] ([[User talk:Tembrel|talk]]) 00:19, 14 November 2019 (UTC)

If you guys like the knapsack problem and simplified stuff, then I've got the game mod for you! https://steamcommunity.com/sharedfiles/filedetails/?id=1844662069 along with https://ktane.timwi.de/HTML/Simon%20Selects.html

(I also tried solving this like I would that mod, but then I realized that this problem is not that.) [[Special:Contributions/172.69.34.24|172.69.34.24]] 03:05, 18 July 2020 (UTC)

;On general solutions
The explanation seems to assume that general solutions must be in polynomial time, but the comic does not mention that. It seemed to me that finding a non-polynomial general solution (which exist, obviously, with one even described in the explanation) *still* gets a 50% tip, which also means the 50% tip is a lot more reasonable now. While mentioning that no polynomial GS exists is probably still a good idea, it seems to me that the explanation should not assume one is neccessary for the tip. [[Special:Contributions/172.68.238.109|172.68.238.109]] 00:59, 24 October 2022 (UTC)

== Should this be in the Multiple Cueballs category? ==

The guy ordering, plus his companion and the waiter are all cueballs, unless I've misunderstood. [[User:WikipedianPolitician|WikipedianPolitician]] ([[User talk:WikipedianPolitician|talk]]) 23:45, 24 March 2026 (UTC)