NP (complexity): Revision history

6 July 2024

• curprev 18:4118:41, 6 July 2024‎ XOR'easter talk contribs‎ 21,006 bytes +31‎ reduce by 1 the number of endnotes in the intro; avoid overloading the term "problem" to mean both specific decision problems and the general P-vs-NP question undo

9 June 2024

• curprev 17:1517:15, 9 June 2024‎ Dexxor talk contribs‎ m 20,975 bytes +1‎ Undid revision 1228057634 by 2601:40F:4400:1E30:8C2C:20D9:61BB:B3C3 (talk) undo Tag: Undo
• curprev 07:0807:08, 9 June 2024‎ 2601:40f:4400:1e30:8c2c:20d9:61bb:b3c3 talk‎ 20,974 bytes −1‎ No edit summary undo Tag: Reverted

7 May 2024

• curprev 14:5014:50, 7 May 2024‎ 94.33.162.86 talk‎ 20,975 bytes −3‎ No edit summary undo Tag: Manual revert
• curprev 14:4914:49, 7 May 2024‎ 94.33.162.86 talk‎ 20,978 bytes +3‎ No edit summary undo Tag: Reverted

9 November 2023

• curprev 03:0403:04, 9 November 2023‎ Kvng talk contribs‎ 20,975 bytes +4‎ caps. link. undo

27 September 2023

• curprev 15:0915:09, 27 September 2023‎ Citation bot talk contribs‎ 20,971 bytes −25‎ Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | #UCB_CommandLine undo

18 August 2023

• curprev 18:0418:04, 18 August 2023‎ Eduardogbg talk contribs‎ 20,996 bytes −5‎ Undid revision 1171041969 by Eduardogbg (talk) undo Tag: Undo
• curprev 17:5817:58, 18 August 2023‎ Eduardogbg talk contribs‎ m 21,001 bytes +5‎ fix the reference to nondeterministic Turing machines, from nondeterministic algorithms (as in computer programming). undo Tag: Reverted

15 August 2023

• curprev 00:5900:59, 15 August 2023‎ OAbot talk contribs‎ m 20,996 bytes +17‎ Open access bot: doi updated in citation with #oabot. undo

6 June 2023

• curprev 21:4221:42, 6 June 2023‎ Yehuling talk contribs‎ m 20,979 bytes +86‎ fixed a typo – the start of the second paragraph previously said NP is class of problems verifiable in poly time on a non-deterministic Turing Machine (with a link) which is misleading – the definition is verifiable in poly time on a deterministic TM. So I edited that and made the writing clearer to the reader by adding bullet points so the differences between the definitions can be easily seen. undo Tag: Visual edit

29 April 2023

• curprev 20:0120:01, 29 April 2023‎ Grant-hale talk contribs‎ 20,893 bytes +2‎ solvable to verifiable (https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard) undo Tag: Visual edit

15 March 2023

• curprev 21:4821:48, 15 March 2023‎ Citation bot talk contribs‎ 20,891 bytes +67‎ Add: isbn, doi, pages, s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. Upgrade ISBN10 to 13. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_CommandLine undo

1 March 2023

• curprev 03:5203:52, 1 March 2023‎ Siddharthist talk contribs‎ 20,824 bytes +227‎ →‎Relationship to other classes: Add inclusion diagram undo Tag: 2017 wikitext editor
• curprev 02:5802:58, 1 March 2023‎ Siddharthist talk contribs‎ 20,597 bytes +541‎ →‎Relationship to other classes: Copy paragraph about relationship to BPP from BPP page undo Tag: 2017 wikitext editor

28 February 2023

• curprev 22:2622:26, 28 February 2023‎ Siddharthist talk contribs‎ 20,056 bytes +116‎ →‎Relationship to other classes: Add image undo Tag: 2017 wikitext editor
• curprev 22:1122:11, 28 February 2023‎ Siddharthist talk contribs‎ 19,940 bytes +229‎ →‎Examples: Group NP-complete examples, link to main list undo Tag: 2017 wikitext editor

2 November 2022

• curprev 23:5923:59, 2 November 2022‎ Mikhail Ryazanov talk contribs‎ m 19,711 bytes +126‎ →‎Relationship to other classes: fmt., (dead link) undo
• curprev 23:5323:53, 2 November 2022‎ Mikhail Ryazanov talk contribs‎ m 19,585 bytes +11‎ →‎Why some NP problems are hard to solve: punct. undo
• curprev 23:5223:52, 2 November 2022‎ Mikhail Ryazanov talk contribs‎ m 19,574 bytes +1‎ →‎Properties: punct. undo
• curprev 23:5023:50, 2 November 2022‎ Mikhail Ryazanov talk contribs‎ m 19,573 bytes +11‎ →‎Verifier-based definition: punct., style undo
• curprev 23:4723:47, 2 November 2022‎ Mikhail Ryazanov talk contribs‎ m 19,562 bytes +5‎ →‎Formal definition: punct. undo
• curprev 23:4623:46, 2 November 2022‎ Mikhail Ryazanov talk contribs‎ m 19,557 bytes +182‎ →‎top: punct., style undo

3 October 2022

• curprev 14:1614:16, 3 October 2022‎ RealLifeRobot talk contribs‎ 19,375 bytes −7‎ Restored revision 1102809447 by Mgkrupa (talk): Test edit, I guess undo Tags: Twinkle Undo
• curprev 12:4212:42, 3 October 2022‎ 2405:204:8308:b250:1759:ff65:771f:51ae talk‎ 19,382 bytes +7‎ No edit summary undo Tags: Reverted Mobile edit Mobile web edit

7 August 2022

• curprev 00:5900:59, 7 August 2022‎ Mgkrupa talk contribs‎ 19,375 bytes +21‎ Added {{Mathematical logic}} undo
• curprev 00:5900:59, 7 August 2022‎ Mgkrupa talk contribs‎ 19,354 bytes +14‎ →‎See also undo

3 July 2022

• curprev 21:3621:36, 3 July 2022‎ Zaslav talk contribs‎ m 19,340 bytes −1‎ →‎Why some NP problems are hard to solve: Ce undo Tag: Manual revert

28 May 2022

• curprev 23:5823:58, 28 May 2022‎ Suffusion of Yellow talk contribs‎ m 19,341 bytes +2,056‎ rv mass unexplained blanking undo Tags: Rollback Reverted
• curprev 23:4723:47, 28 May 2022‎ 102.250.1.14 talk‎ 17,285 bytes −2,056‎ No edit summary undo Tags: Reverted references removed Visual edit Mobile edit Mobile web edit

20 May 2022

• curprev 20:4420:44, 20 May 2022‎ 2a02:3038:11:9985:1:2:5ca9:9032 talk‎ 19,341 bytes +1‎ →‎Why some NP problems are hard to solve: Fixed typo undo Tags: Reverted canned edit summary Mobile edit Mobile app edit Android app edit

9 May 2022

• curprev 14:3014:30, 9 May 2022‎ Uwsi talk contribs‎ m 19,340 bytes +1‎ →‎Example undo

6 April 2022

• curprev 07:5307:53, 6 April 2022‎ Suhacker256 talk contribs‎ m 19,339 bytes −101‎ →‎Verifier-based definition: Remove redundant sentence about the subset sum problem undo Tag: Visual edit
• curprev 02:3702:37, 6 April 2022‎ Thatsme314 talk contribs‎ m 19,440 bytes 0‎ →‎Relationship to other classes: present tense undo

5 January 2022

• curprev 05:4005:40, 5 January 2022‎ 589q talk contribs‎ 19,440 bytes +4‎ →‎Equivalence of definitions undo

29 September 2021

• curprev 09:0809:08, 29 September 2021‎ Hamled talk contribs‎ m 19,436 bytes −10‎ Change instances of 'non-deterministic' to 'nondeterministic', to match other articles. undo
• curprev 05:4805:48, 29 September 2021‎ Cedar101 talk contribs‎ 19,446 bytes −4‎ →‎Formal definition: fix math italic undo

22 June 2021

• curprev 16:3416:34, 22 June 2021‎ Abrahammurciano talk contribs‎ 19,450 bytes −188‎ removed false statement. problems do not "change" complexity classes as we discover more efficient algorithms. if we find a polynomial algorithms for a problem not known to be in P, we now know that it is also in P, but it does not cease to be an element of NP, since P is a subset of NP. undo

14 May 2021

• curprev 03:5403:54, 14 May 2021‎ Duckmather talk contribs‎ 19,638 bytes +114‎ corrected errata in page based on 31.205.55.139's talkpage comment undo Tag: Visual edit

8 May 2021

• curprev 22:2422:24, 8 May 2021‎ Mandarax talk contribs‎ m 19,524 bytes −1‎ Correct spelling undo Tag: AWB

2 May 2021

• curprev 20:2120:21, 2 May 2021‎ 212.201.44.244 talk‎ 19,525 bytes +4‎ Small blunder undo

13 April 2021

• curprev 20:5120:51, 13 April 2021‎ Duckmather talk contribs‎ 19,521 bytes +651‎ →‎Example: added citations; COI DISCLAIMER: I'm also a commenter on Scott Aaronson's blog undo Tag: Visual edit

1 April 2021

• curprev 12:4512:45, 1 April 2021‎ Comp.arch talk contribs‎ m 18,870 bytes +2‎ No edit summary undo Tag: 2017 wikitext editor

17 January 2021

• curprev 22:3222:32, 17 January 2021‎ Huggums537 talk contribs‎ 18,868 bytes +74‎ Adding local short description: "Complexity class used to classify decision problems", overriding Wikidata description "computational complexity class of decision problems solvable by a non-deterministic Turing machine in polynomial time" (Shortdesc helper) undo

3 January 2021

• curprev 23:4623:46, 3 January 2021‎ Lucca Mito talk contribs‎ m 18,794 bytes −21‎ Reverted redundant link undo Tags: Manual revert Visual edit Mobile edit Mobile web edit
• curprev 23:4523:45, 3 January 2021‎ Lucca Mito talk contribs‎ m 18,815 bytes +21‎ No edit summary undo Tags: Reverted Visual edit Mobile edit Mobile web edit

2 January 2021

• curprev 21:0321:03, 2 January 2021‎ Jasper Deng talk contribs‎ m 18,794 bytes −48‎ Reverted edits by Susheel.M 1 (talk) to last version by Jasper Deng undo Tag: Rollback
• curprev 14:0414:04, 2 January 2021‎ Susheel.M 1 talk contribs‎ 18,842 bytes +48‎ No edit summary undo Tag: Reverted
• curprev 13:4913:49, 2 January 2021‎ Jasper Deng talk contribs‎ m 18,794 bytes −33‎ Reverted edits by 2409:4042:9C:7D19:C81:311D:BF2B:6B8D (talk) to last version by Monkbot undo Tag: Rollback
• curprev 13:4613:46, 2 January 2021‎ 2409:4042:9c:7d19:c81:311d:bf2b:6b8d talk‎ 18,827 bytes +33‎ P=NP undo Tag: Reverted