287: NP-Complete - Revision history

WikipedianPolitician: added category!

2026-03-25T00:19:27Z

added category!

Lettherebedarklight: /* Trivia */ add Category:Comics with a Spanish translation

2025-12-15T09:00:32Z

‎Trivia: add Category:Comics with a Spanish translation

162.246.94.131: /* Explanation */

2025-10-29T01:49:43Z

‎Explanation

162.246.94.131: /* Explanation */

2025-10-29T00:14:01Z

‎Explanation

FaviFake: rm as unclear, From the [[explain xkcd:Editor FAQ#citation|Editor FAQ § [Citation needed]:]] "This template should only be placed when there is a deeper sense of humor and should not be overused."

2025-10-01T16:15:09Z

rm as unclear, From the Editor FAQ § [Citation needed]: "This template should only be placed when there is a deeper sense of humor and should not be overused."

82.132.217.183: /* Explanation / Recorrecting punctuation. (But "slightly less than fair" to whom*? Not entirely sure of the perspective. Even/especially with the add-on.)

2025-09-30T14:18:29Z

‎Explanation: Recorrecting punctuation. (But "slightly less than fair" to *whom*? Not entirely sure of the perspective. Even/especially with the add-on.)

Mathmaster: /* Explanation */

2025-09-29T22:35:35Z

‎Explanation

Hatman31: /* Trivia */ Replaced dead link with archive

2024-08-09T20:50:05Z

‎Trivia: Replaced dead link with archive

162.158.33.151: /* Explanation */

2024-03-19T09:48:29Z

‎Explanation

172.70.38.9: /* Trivia */ trivial answer explanation from xkcd volume 0

2024-01-01T14:31:36Z

‎Trivia: trivial answer explanation from xkcd volume 0

← Older revision		Revision as of 00:19, 25 March 2026
Line 56:		Line 56:
	[[Category:Programming]]		[[Category:Programming]]
	[[Category:Comics with a Spanish translation]]		[[Category:Comics with a Spanish translation]]
		+	[[Category:Multiple Cueballs]]

← Older revision		Revision as of 09:00, 15 December 2025
Line 55:		Line 55:
	[[Category:Math]]		[[Category:Math]]
	[[Category:Programming]]		[[Category:Programming]]
		+	[[Category:Comics with a Spanish translation]]

@@ Line 18: / Line 18: @@
 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 combinations of appetizers that total $15.05 and solve the problem posed in the comic strip:
+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)

@@ Line 18: / Line 18: @@
 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:
+For those curious, there are 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)

@@ Line 16: / Line 16: @@
 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,{{cn}} unless the order is very large.
+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:

@@ Line 47: / Line 47: @@
 *"Chotchkies" (slightly misspelt) is Yiddish slang for little accessories and trinkets. It is also the name of the restaurant in the 1999 Mike Judge-directed comedy ''{{w|Office Space}}''.
-*In [http://www.maa.org/mathhorizons/MH-Sep2012_XKCD.html an interview] with the Mathematical Association of America, Randall said that the trivial answer to this problem was a mistake. <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").
+*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}}

287: NP-Complete - Revision history

WikipedianPolitician: added category!

Lettherebedarklight: /* Trivia */ add Category:Comics with a Spanish translation

162.246.94.131: /* Explanation */

162.246.94.131: /* Explanation */

FaviFake: rm as unclear, From the [[explain xkcd:Editor FAQ#citation|Editor FAQ § [Citation needed]:]] "This template should only be placed when there is a deeper sense of humor and should not be overused."

82.132.217.183: /* Explanation */ Recorrecting punctuation. (But "slightly less than fair" to *whom*? Not entirely sure of the perspective. Even/especially with the add-on.)

Mathmaster: /* Explanation */

Hatman31: /* Trivia */ Replaced dead link with archive

162.158.33.151: /* Explanation */

172.70.38.9: /* Trivia */ trivial answer explanation from xkcd volume 0

82.132.217.183: /* Explanation / Recorrecting punctuation. (But "slightly less than fair" to whom*? Not entirely sure of the perspective. Even/especially with the add-on.)