Strong NP-completeness: Revision history

Filter revisionsshowhide

To date:

Tag filter:

Invert selection

External tools:

For any version listed below, click on its date to view it. For more help, see Help:Page history and Help:Edit summary. (cur) = difference from current version, (prev) = difference from preceding version, m = minor edit, → = section edit, ← = automatic edit summary

curprev 16:1316:13, 29 May 2025 Hbecker.inf talk contribs 4,696 bytes +627 The paragraph about reduction is imprecise to the point of being wrong. What is called and used as a polynomial reduction in NP-hardness proofs does not meet the necessary bar to prove STRONG NP-hardness. Otherwise, the proof of 3SAT to Subset-Sum in Sipser would prove subset-sum to be a Strongly NP-hard problem. undo

curprev 11:1911:19, 28 August 2022 Citation bot talk contribs 4,043 bytes +16 Add: s2cid. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 2083/3850 undo

curprev 03:5803:58, 23 December 2020 Monkbot talk contribs m 4,063 bytes −15 Task 18 (cosmetic): eval 4 templates: del empty params (2×); hyphenate params (4×); del |ref=harv (1×); undo Tag: AWB

curprev 09:3809:38, 6 November 2020 Jochen Burghardt talk contribs 4,058 bytes −214 →top: rm vague and misleading sentence: "relatively small" doesn't say much, and e.g. the strongly NP-complete SAT problem, too, has efficient solutions for small inputs, see the SAT competitions, e.g. Boolean_satisfiability_problem#Algorithms_for_solving_SAT undo
curprev 09:2109:21, 6 November 2020 Jochen Burghardt talk contribs 4,272 bytes +9 →top: better spell out what "so" refers to undo

curprev 22:5222:52, 13 July 2019 Citation bot talk contribs m 4,203 bytes +32 Alter: title. Add: title-link. Removed URL that duplicated unique identifier. | You can use this bot yourself. Report bugs here.| Activated by User:Marianne Zimmerman undo

curprev 17:3317:33, 30 May 2017 Xie1995 talk contribs 4,167 bytes −105 Removed redundant statement; moved citation undo

curprev 20:4420:44, 7 February 2017 172.97.98.42 talk 4,272 bytes −1 acronym was used before full phrase undo

curprev 23:5623:56, 18 January 2015 31.19.114.20 talk 4,241 bytes +11 corrected knapsack-problem being solveable in polynomial time, its actually pseudo-polynomial time undo

curprev 19:0019:00, 23 March 2013 Addbot talk contribs m 4,259 bytes −68 Bot: Migrating 2 interwiki links, now provided by Wikidata on d:q7624684 undo

curprev 13:1613:16, 12 October 2012 Yobot talk contribs m 4,327 bytes −18 WP:CHECKWIKI error 61 fix, References after punctuation per WP:REFPUNC and WP:PAIC using AWB (8459) undo

curprev 12:3212:32, 18 June 2012 82.52.99.48 talk 4,345 bytes −9 strongly NP-complete in the strong sense > NP-complete in the strong sense undo

curprev 15:2615:26, 27 March 2011 Kiefer.Wolfowitz talk contribs 4,315 bytes +284 Strongly NP-hard, following Papadimitriou and Steiglitz undo

curprev 20:5420:54, 20 March 2011 Kiefer.Wolfowitz talk contribs 4,031 bytes +284 Wickiformat {{cite book|last1=Garey|first1=M. R.|authorlink1=Michael R. Garey|last2=Johnson|first2=D. S.|authorlink2=David S. Johnson|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|year=1979 |isbn=0-7167-10 undo