Exponential time hypothesis: Revision history

5 April 2024

• curprev 04:0604:06, 5 April 2024‎ 74.109.239.216 talk‎ 22,318 bytes 0‎ No edit summary undo

4 April 2024

• curprev 12:0612:06, 4 April 2024‎ PrimeBOT talk contribs‎ m 22,318 bytes −1‎ →‎top: Task 44 (trial): clean up shortdesc whitespace issues undo Tag: AWB

23 March 2024

• curprev 22:5222:52, 23 March 2024‎ InternetArchiveBot talk contribs‎ 22,319 bytes +193‎ Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5 undo

11 January 2024

• curprev 06:3906:39, 11 January 2024‎ Sir Ibee talk contribs‎ 22,126 bytes +29‎ Open access status updates in citations with OAbot #oabot undo Tag: OAbot [2.1]

28 December 2023

• curprev 19:2819:28, 28 December 2023‎ AB-Babayo talk contribs‎ 22,097 bytes +31‎ Added free to read link in citations with OAbot #oabot undo Tag: OAbot [2.1]

10 December 2023

• curprev 14:2614:26, 10 December 2023‎ Citation bot talk contribs‎ 22,066 bytes +128‎ Add: s2cid. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 358/1612 undo

19 October 2023

• curprev 22:3922:39, 19 October 2023‎ David Eppstein talk contribs‎ 21,938 bytes +24‎ Undid revision 1180952501 by Jochen Burghardt (talk) got the quantifiers backwards. It is definitely true that such an algorithm exists with epsilon=1. undo
• curprev 21:4821:48, 19 October 2023‎ Jochen Burghardt talk contribs‎ 21,914 bytes +75‎ →‎top: attempt to fix spelling-out of "subexp. time" undo
• curprev 21:3821:38, 19 October 2023‎ Jochen Burghardt talk contribs‎ 21,839 bytes −48‎ No edit summary undo Tag: Undo
• curprev 21:3321:33, 19 October 2023‎ 173.75.1.61 talk‎ 21,887 bytes −2‎ typo undo Tag: Reverted
• curprev 21:3121:31, 19 October 2023‎ 173.75.1.61 talk‎ 21,889 bytes +5‎ typo undo Tag: Reverted
• curprev 21:3121:31, 19 October 2023‎ 173.75.1.61 talk‎ 21,884 bytes +45‎ fixed statement. -- R.O'D. undo Tag: Reverted

9 June 2023

• curprev 12:3512:35, 9 June 2023‎ Fnareoh talk contribs‎ 21,839 bytes +4‎ No edit summary undo

25 March 2023

• curprev 18:4018:40, 25 March 2023‎ Fortnow talk contribs‎ 21,835 bytes +46‎ Put in a simple precise definition in the first paragraph. undo

29 January 2023

• curprev 06:2906:29, 29 January 2023‎ OAbot talk contribs‎ m 21,789 bytes +42‎ Open access bot: doi, arxiv added to citation with #oabot. undo

19 October 2022

• curprev 17:4317:43, 19 October 2022‎ David Eppstein talk contribs‎ 21,747 bytes +61‎ ce undo
• curprev 13:0013:00, 19 October 2022‎ Jochen Burghardt talk contribs‎ 21,686 bytes +26‎ →‎Definition: fix typo in CNF def.; insert clarifying "all" quantifier; according to the abstract of Schoning.1999, WalkSAT is a probabilistic alg. and its average time complexity has been proven; BTW: reducing the number of big- and little-o uses (if possible) would increase understandability undo
• curprev 06:0706:07, 19 October 2022‎ David Eppstein talk contribs‎ 21,660 bytes +22‎ →‎Satisfiability: brute-force search undo
• curprev 06:0606:06, 19 October 2022‎ David Eppstein talk contribs‎ 21,638 bytes +11‎ →‎Satisfiability: repeat foot undo
• curprev 06:0506:05, 19 October 2022‎ David Eppstein talk contribs‎ 21,627 bytes +655‎ source nonuniform undo
• curprev 05:5705:57, 19 October 2022‎ David Eppstein talk contribs‎ 20,972 bytes +96‎ →‎Notes: more metadata undo
• curprev 05:5005:50, 19 October 2022‎ David Eppstein talk contribs‎ 20,876 bytes +106‎ →‎Definition: display the walksat time bound; it's too big an expression to inline undo
• curprev 05:4705:47, 19 October 2022‎ David Eppstein talk contribs‎ m 20,770 bytes +25‎ →‎Definition: show the limit as a mathematics formula undo
• curprev 05:4505:45, 19 October 2022‎ David Eppstein talk contribs‎ 20,745 bytes +570‎ →‎Definition: gloss cnf; ce undo
• curprev 01:1401:14, 19 October 2022‎ David Eppstein talk contribs‎ 20,175 bytes +849‎ Add some nowraps; other copyedits undo
• curprev 01:0401:04, 19 October 2022‎ David Eppstein talk contribs‎ 19,326 bytes −30‎ no need for separate footnotes and refs, merge; add discussion of WalkSAT undo

21 August 2022

• curprev 07:2007:20, 21 August 2022‎ David Eppstein talk contribs‎ 19,356 bytes +84‎ →‎top: also implies near-optimal time complexity undo
• curprev 01:5101:51, 21 August 2022‎ David Eppstein talk contribs‎ 19,272 bytes −35‎ →‎Other search problems: feedback arc set problem on tournaments; avoid offbeat O-notation undo
• curprev 01:4801:48, 21 August 2022‎ David Eppstein talk contribs‎ 19,307 bytes +35‎ →‎Structural complexity: Padding argument undo
• curprev 00:0900:09, 21 August 2022‎ David Eppstein talk contribs‎ 19,272 bytes +298‎ math formatting undo

20 August 2022

• curprev 21:2021:20, 20 August 2022‎ David Eppstein talk contribs‎ 18,974 bytes −41‎ section structure undo

30 May 2022

• curprev 15:3715:37, 30 May 2022‎ AnomieBOT talk contribs‎ 19,015 bytes +32‎ Rescuing orphaned refs ("w03" from rev 1058711320) undo
• curprev 13:2913:29, 30 May 2022‎ Stankovic.s.aleksa talk contribs‎ m 18,983 bytes −536‎ Removed sentence saying that Independent Set can be solved in sub-exponential time since this is not true (and contradicts ETH). undo Tag: references removed

5 December 2021

• curprev 03:5403:54, 5 December 2021‎ Rlink2 talk contribs‎ m 19,519 bytes +3‎ →‎References: archive link repair, may include: archive.* -> archive.today, and http->https for ghostarchive.org and archive.org (wp:el#Specifying_protocols) undo Tag: AWB

24 November 2021

• curprev 16:5016:50, 24 November 2021‎ Badboul talk contribs‎ 19,516 bytes −98‎ removed k=2 from Definition of s_k as it was incorrect. It does not hold s_2 = 0 as 2-SAT is not in O(1). In the original paper s_k is also only defined for k>=3. undo Tag: Visual edit: Switched

30 October 2021

• curprev 17:1117:11, 30 October 2021‎ Maxeto0910 talk contribs‎ 19,614 bytes +66‎ Added short description. undo Tags: Mobile edit Mobile web edit Advanced mobile edit

17 February 2021

• curprev 06:5206:52, 17 February 2021‎ Jakas1 talk contribs‎ m 19,548 bytes +20‎ Disambiguated: Mihai Pătraşcu → Mihai Pătrașcu (computer scientist) using Dab solver undo

13 April 2020

• curprev 18:1618:16, 13 April 2020‎ OAbot talk contribs‎ m 19,528 bytes +21‎ Open access bot: doi added to citation with #oabot. undo

15 December 2019

• curprev 14:0514:05, 15 December 2019‎ Comp.arch talk contribs‎ m 19,507 bytes +9‎ No edit summary undo Tag: 2017 wikitext editor

29 September 2019

• curprev 02:4302:43, 29 September 2019‎ Monkbot talk contribs‎ m 19,498 bytes +3‎ →‎References: Task 16: replaced (2×) / removed (0×) deprecated |dead-url= and |deadurl= with |url-status=; undo Tag: AWB

14 August 2019

• curprev 13:3913:39, 14 August 2019‎ InternetArchiveBot talk contribs‎ 19,495 bytes +211‎ Rescuing 1 sources and tagging 0 as dead. #IABot (v2.0beta15) undo

1 August 2019

• curprev 12:1712:17, 1 August 2019‎ Jochen Burghardt talk contribs‎ 19,284 bytes −22‎ Undid revision 908834242 by 2A00:5BA0:10:2251:224:1DFF:FEDE:83A3 (talk) undo Tag: Undo
• curprev 09:0309:03, 1 August 2019‎ 2a00:5ba0:10:2251:224:1dff:fede:83a3 talk‎ 19,306 bytes +22‎ No edit summary undo

28 July 2019

• curprev 11:1511:15, 28 July 2019‎ Nemo bis talk contribs‎ 19,284 bytes −155‎ redundant URL undo

19 July 2019

• curprev 16:4616:46, 19 July 2019‎ Nemo bis talk contribs‎ 19,439 bytes −223‎ Removed URL that duplicated unique identifier. | You can use this tool yourself. Report bugs here. undo

26 June 2019

• curprev 17:2217:22, 26 June 2019‎ David Eppstein talk contribs‎ 19,662 bytes +117‎ see also Savitch's theorem, showing that a similar exponential gap cannot hold for space complexity undo

23 June 2019

• curprev 14:4514:45, 23 June 2019‎ 192.76.8.80 talk‎ 19,545 bytes −8‎ Removed clearly as it isn't trivial. Might need more explanation! undo

18 April 2019

• curprev 20:0320:03, 18 April 2019‎ David Eppstein talk contribs‎ 19,553 bytes +124‎ complete the thought undo
• curprev 20:0220:02, 18 April 2019‎ David Eppstein talk contribs‎ 19,429 bytes +6‎ repetition of planar is necessary here undo
• curprev 18:5718:57, 18 April 2019‎ Jochen Burghardt talk contribs‎ 19,423 bytes +304‎ →‎top: clarify: not all NP-complete problems are meant here undo