NP-hardness: Revision history

27 June 2024

• curprev 15:2315:23, 27 June 2024‎ Eugenia ioessa talk contribs‎ m 8,594 bytes −64‎ lead ce undo Tag: Visual edit

25 June 2024

• curprev 15:1715:17, 25 June 2024‎ Peaceray talk contribs‎ 8,658 bytes +6‎ Restored revision 1230278055 by ZMBerber (talk): Restoring last known good version undo Tags: Twinkle Undo
• curprev 09:2709:27, 25 June 2024‎ 2001:871:252:6a84:d1a1:68b5:a30d:d894 talk‎ 8,652 bytes −1‎ No edit summary undo Tag: Reverted
• curprev 09:2609:26, 25 June 2024‎ 2001:871:252:6a84:d1a1:68b5:a30d:d894 talk‎ 8,653 bytes −60‎ No edit summary undo Tag: Reverted
• curprev 09:0909:09, 25 June 2024‎ 2600:1005:b0af:4e01:613d:2dbd:7679:a09a talk‎ 8,713 bytes +55‎ No edit summary undo Tags: Reverted Mobile edit Mobile web edit

21 June 2024

• curprev 19:4219:42, 21 June 2024‎ ZMBerber talk contribs‎ m 8,658 bytes 0‎ Typo: "H can be reduced to L" was written, but "L can be reduced to H" was meant. The latter is consistent with the next sentence, the source(s), and what is written later in the Definition section. undo Tag: Manual revert

20 June 2024

• curprev 17:0317:03, 20 June 2024‎ 174.109.107.15 talk‎ 8,658 bytes 0‎ No edit summary undo Tag: Reverted

20 February 2024

• curprev 21:5621:56, 20 February 2024‎ Alexeyevitch talk contribs‎ m 8,658 bytes +2‎ en dash undo
• curprev 19:4919:49, 20 February 2024‎ EXPTIME-complete talk contribs‎ 8,656 bytes +310‎ Added reference to the hierarchy of approximability classes undo

12 February 2024

• curprev 12:3412:34, 12 February 2024‎ Erel Segal talk contribs‎ 8,346 bytes +21‎ No edit summary undo Tag: Visual edit

11 February 2024

• curprev 09:2409:24, 11 February 2024‎ A3nm talk contribs‎ 8,325 bytes 0‎ Typo undo Tags: Mobile edit Mobile web edit Advanced mobile edit

10 February 2024

• curprev 18:3918:39, 10 February 2024‎ Erel Segal talk contribs‎ 8,325 bytes +60‎ No edit summary undo Tag: Visual edit

9 February 2024

• curprev 09:5009:50, 9 February 2024‎ Erel Segal talk contribs‎ 8,265 bytes +46‎ Correct the inaccurate conception that "an NP-hard problem is at least as hard as the hardest problems in NP". undo Tag: Visual edit

12 November 2023

• curprev 01:3301:33, 12 November 2023‎ AlgorithmSoup talk contribs‎ 8,219 bytes −525‎ Removed incorrect oracle-based definition. Note that the source that was cited for the oracle-based definition (see page 135 of the cited book "A First Course in Computability") actually gives the many-one reduction definition (which is the correct one). undo Tag: Visual edit

25 October 2023

• curprev 00:2900:29, 25 October 2023‎ Marc Schroeder talk contribs‎ m 8,744 bytes −283‎ used template {{Garey-Johnson}} undo

9 May 2023

• curprev 15:5215:52, 9 May 2023‎ Emoritz2017 talk contribs‎ 9,027 bytes +119‎ Added →‎See Also: section undo

1 May 2023

• curprev 01:0801:08, 1 May 2023‎ 2600:4040:a15d:e300:c1ec:a05e:ed1b:856a talk‎ 8,908 bytes −11‎ →‎removed awkwardly place, opinionated word "awkwardly" undo

28 February 2023

• curprev 22:1822:18, 28 February 2023‎ Siddharthist talk contribs‎ 8,919 bytes −32‎ →‎Examples: Subset sum is also NP-complete undo Tag: 2017 wikitext editor
• curprev 22:1722:17, 28 February 2023‎ Siddharthist talk contribs‎ 8,951 bytes +94‎ →‎Examples: Note that all NP-complete problems are NP-hard, so all examples of NP-completeness are examples of NP-hardness undo Tag: 2017 wikitext editor

24 January 2023

• curprev 00:4000:40, 24 January 2023‎ Peaceray talk contribs‎ 8,857 bytes −112‎ Reverting edit(s) by Bentlystewart (talk) to rev. 1098421480 by Ivancr72: Not providing a reliable source (RW 16.1) undo Tags: RW Undo

23 January 2023

• curprev 20:4020:40, 23 January 2023‎ Bentlystewart talk contribs‎ m 8,969 bytes +112‎ I added an example of an NP-hard problem. undo Tags: Reverted Visual edit Mobile edit Mobile web edit

15 July 2022

• curprev 19:2419:24, 15 July 2022‎ Ivancr72 talk contribs‎ m 8,857 bytes −3‎ add space before apostrophe undo Tag: 2017 wikitext editor

9 May 2022

• curprev 14:3414:34, 9 May 2022‎ Uwsi talk contribs‎ 8,860 bytes −493‎ The reference doesn't does any mention about this misconception undo

30 January 2022

• curprev 23:1023:10, 30 January 2022‎ FrogFlint talk contribs‎ m 9,353 bytes −16‎ changed "<math>\neq</math>" to "≠" in link text undo

27 January 2022

• curprev 23:2623:26, 27 January 2022‎ BattyBot talk contribs‎ m 9,369 bytes −6‎ Fixed CS1 errors: extra text: volume and general fixes undo Tag: AWB

28 May 2021

• curprev 04:1604:16, 28 May 2021‎ 70.234.252.225 talk‎ 9,375 bytes +1‎ →‎Examples undo Tags: Mobile edit Mobile web edit

1 May 2021

• curprev 19:0919:09, 1 May 2021‎ Dirkbb talk contribs‎ m 9,374 bytes −23‎ Reverted 1 edit by 37.156.232.211 (talk) to last revision by Citation bot undo Tags: Twinkle Undo
• curprev 18:4718:47, 1 May 2021‎ 37.156.232.211 talk‎ 9,397 bytes +23‎ →‎Definition undo Tag: Reverted

12 April 2021

• curprev 13:2813:28, 12 April 2021‎ Citation bot talk contribs‎ 9,374 bytes +15‎ Add: s2cid. | Use this bot. Report bugs. | Suggested by Grimes2 | Category:CS1 errors: extra text: volume | via #UCB_Category 1530/2451 undo

26 March 2021

• curprev 20:5220:52, 26 March 2021‎ Todd Bezenek talk contribs‎ 9,359 bytes +2‎ →‎NP-naming convention: I changed "a given yes solution" to "any given yes solution" to make the statement more clear. undo

17 December 2020

• curprev 01:2501:25, 17 December 2020‎ 2600:1017:b802:4556:d9d6:9be:7daf:2752 talk‎ 9,357 bytes +3‎ →‎Consequences: I could not improve the page without solving the NP-Hard problem of converting all “cannot” to “could not”. However, the reversion will be faster than me. undo Tags: Mobile edit Mobile web edit

10 December 2020

• curprev 17:1517:15, 10 December 2020‎ Monkbot talk contribs‎ m 9,354 bytes −19‎ Task 18 (cosmetic): eval 10 templates: del empty params (3×); undo Tag: AWB

24 November 2020

• curprev 21:3321:33, 24 November 2020‎ Staticshakedown talk contribs‎ 9,373 bytes +39‎ Importing Wikidata short description: "Complexity class" (Shortdesc helper) undo

7 August 2020

• curprev 16:5116:51, 7 August 2020‎ GreenC bot talk contribs‎ 9,334 bytes 0‎ Reformat 1 archive link. Wayback Medic 2.5 undo

19 May 2020

• curprev 19:5819:58, 19 May 2020‎ 84.213.189.169 talk‎ 9,334 bytes 0‎ typo fix undo

18 May 2020

• curprev 07:4107:41, 18 May 2020‎ Jaydavidmartin talk contribs‎ m 9,334 bytes +20‎ added wikilink undo
• curprev 05:0005:00, 18 May 2020‎ Jaydavidmartin talk contribs‎ 9,314 bytes +50‎ adjusted sentence on finding a polynomial time algorithm for an NP-hard problem undo
• curprev 04:5504:55, 18 May 2020‎ Jaydavidmartin talk contribs‎ m 9,264 bytes −1‎ adjusted formatting of first sentence undo

11 March 2020

• curprev 19:5319:53, 11 March 2020‎ Citation bot talk contribs‎ m 9,265 bytes −66‎ Alter: title. Add: title-link, year. Removed URL that duplicated unique identifier. Removed accessdate with no specified URL. | You can use this bot yourself. Report bugs here. | Activated by User:AManWithNoPlan | All pages linked from User:AManWithNoPlan/sandbox2. undo

8 March 2020

• curprev 17:4317:43, 8 March 2020‎ 216.232.145.121 talk‎ 9,331 bytes +10‎ No edit summary undo

12 December 2019

• curprev 15:1215:12, 12 December 2019‎ 37.74.30.146 talk‎ 9,321 bytes −1‎ No edit summary undo

20 November 2019

• curprev 18:1618:16, 20 November 2019‎ Cpt Wise talk contribs‎ m 9,322 bytes 0‎ →‎Definition undo

18 November 2019

• curprev 20:4620:46, 18 November 2019‎ Gascenciom98 talk contribs‎ 9,322 bytes +28‎ →‎Definition undo

5 November 2019

• curprev 16:0216:02, 5 November 2019‎ Mauls talk contribs‎ 9,294 bytes 0‎ →‎Examples undo Tags: Mobile edit Mobile web edit Advanced mobile edit

14 September 2019

• curprev 22:3222:32, 14 September 2019‎ 24.37.54.254 talk‎ 9,294 bytes −46‎ No edit summary undo

8 September 2019

• curprev 12:0612:06, 8 September 2019‎ InternetArchiveBot talk contribs‎ 9,340 bytes +61‎ Bluelinking 1 books for verifiability.) #IABot (v2.1alpha3 undo

18 July 2019

• curprev 11:4311:43, 18 July 2019‎ Trappist the monk talk contribs‎ m 9,279 bytes −71‎ →‎top: cite repair; undo
• curprev 05:5205:52, 18 July 2019‎ 2806:104e:17:5044:9d2d:e71c:b31f:ca9b talk‎ 9,350 bytes −9‎ "Awkwardly, it does not restrict the class NP-hard to decision problems", so NP-Hard are not necessarily decision problems undo

16 July 2019

• curprev 03:1303:13, 16 July 2019‎ I Hate Banner adds talk contribs‎ m 9,359 bytes +233‎ Added link to archive copy of a citation because original link was dead. undo Tag: Visual edit

20 April 2019

• curprev 00:3900:39, 20 April 2019‎ Scrabbler94 talk contribs‎ m 9,126 bytes +37‎ link to non-deterministic TMs undo