Talk:287: NP-Complete - Revision history

WikipedianPolitician at 00:21, 25 March 2026

2026-03-25T00:21:10Z

81.179.199.253 at 00:16, 25 March 2026

2026-03-25T00:16:35Z

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

2026-03-24T23:46:56Z

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

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

2026-03-24T23:45:58Z

‎Should this be in the Multiple Cueballs category?

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

2026-03-24T23:45:01Z

‎Should this be in the Multiple Cueballs category?: new section

172.69.130.236 at 12:37, 20 May 2025

2025-05-20T12:37:00Z

ProfDigory: Found another solution

2024-07-10T01:07:25Z

Found another solution

172.68.238.109 at 00:59, 24 October 2022

2022-10-24T00:59:01Z

172.69.34.24 at 03:08, 18 July 2020

2020-07-18T03:08:06Z

172.69.34.24 at 03:05, 18 July 2020

2020-07-18T03:05:56Z

← Older revision		Revision as of 00:21, 25 March 2026
Line 138:		Line 138:
	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)		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)		: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)

@@ Line 134: / Line 134: @@
 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? ====
+;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)

@@ Line 134: / Line 134: @@
 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? ===
+==== 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)

@@ Line 134: / Line 134: @@
 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? ==
+=== 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)

← Older revision		Revision as of 23:45, 24 March 2026
Line 133:		Line 133:
	;On general solutions		;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)		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)

← Older revision		Revision as of 12:37, 20 May 2025
Line 25:		Line 25:

	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)		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		;Not the knapsack problem

@@ Line 23: / Line 23: @@
 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]]
 ;Not the knapsack problem

← Older revision		Revision as of 00:59, 24 October 2022
Line 127:		Line 127:

	(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)		(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)

← Older revision		Revision as of 03:08, 18 July 2020
Line 124:		Line 124:
	TSP is NP-hard, not NP-complete [[User:Tembrel\|Tembrel]] ([[User talk:Tembrel\|talk]]) 00:19, 14 November 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 [[Special:Contributions/172.69.34.24\|172.69.34.24]] 03:05, 18 July 2020 (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)

← Older revision		Revision as of 03:05, 18 July 2020
Line 123:		Line 123:

	TSP is NP-hard, not NP-complete [[User:Tembrel\|Tembrel]] ([[User talk:Tembrel\|talk]]) 00:19, 14 November 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 [[Special:Contributions/172.69.34.24\|172.69.34.24]] 03:05, 18 July 2020 (UTC)