St-connectivity: Revision history

8 April 2024

• curprev 23:4523:45, 8 April 2024‎ Totallynotpetebuttigieg talk contribs‎ m 3,716 bytes −6‎ Reingold proved that USTCON is in L, not that USTCON is L-complete. The former was/is extremely challenging, the latter not so much. undo

19 October 2022

• curprev 01:2101:21, 19 October 2022‎ David Eppstein talk contribs‎ 3,722 bytes +13‎ →‎Complexity: ce undo
• curprev 01:2001:20, 19 October 2022‎ David Eppstein talk contribs‎ 3,709 bytes +443‎ →‎Complexity: mention linear-time sequential solutions undo

23 May 2020

• curprev 05:1105:11, 23 May 2020‎ David Eppstein talk contribs‎ 3,266 bytes +38‎ Descriptive Complexity undo

11 September 2019

• curprev 14:1314:13, 11 September 2019‎ Aravindreddy96 talk contribs‎ 3,228 bytes −40‎ Computational Complexity Theory is a part of computer science. Saying "in CS and CCT" provides no more information than saying "in CS". undo

10 January 2019

• curprev 18:0918:09, 10 January 2019‎ Freshman404 talk contribs‎ 3,268 bytes +32‎ →‎top undo

22 August 2017

• curprev 21:5721:57, 22 August 2017‎ Noamz talk contribs‎ 3,236 bytes +39‎ →‎Complexity: clarification undo

8 September 2016

• curprev 06:5606:56, 8 September 2016‎ Cedar101 talk contribs‎ m 3,197 bytes +16‎ {{mset}}, {{angbr}} undo

12 October 2015

• curprev 10:0110:01, 12 October 2015‎ Dricherby talk contribs‎ 3,181 bytes +7‎ No need to give such prominence to the now-defunct class SL. Better to say that Reingold proved it's L-complete, so SL=L. undo

14 March 2013

• curprev 17:4317:43, 14 March 2013‎ Addbot talk contribs‎ m 3,174 bytes −66‎ Bot: Migrating 2 interwiki links, now provided by Wikidata on d:q1361537 undo

5 December 2012

• curprev 22:5722:57, 5 December 2012‎ 128.205.70.155 talk‎ 3,240 bytes +39‎ adding wikipedia link to Michael Sipser undo

13 December 2011

• curprev 23:1323:13, 13 December 2011‎ ZéroBot talk contribs‎ m 3,201 bytes +24‎ r2.7.1) (Robot: Adding pt:Conectividade st undo

14 September 2011

• curprev 01:0401:04, 14 September 2011‎ Twin Bird talk contribs‎ 3,177 bytes +11‎ Discovering a deterministic logspace st-connectivity algorithm would be newsworthy indeed. undo

4 January 2011

• curprev 09:4409:44, 4 January 2011‎ ClueBot NG talk contribs‎ m 3,166 bytes +2,199‎ Reverting possible vandalism by 83.232.98.58 to version by LilHelpa. False positive? Report it. Thanks, ClueBot NG. (158488) (Bot) undo
• curprev 09:4409:44, 4 January 2011‎ 83.232.98.58 talk‎ 967 bytes −2,199‎ →‎Complexity undo

10 April 2010

• curprev 01:3301:33, 10 April 2010‎ LilHelpa talk contribs‎ m 3,166 bytes −4‎ fixed "the the" undo

26 March 2010

• curprev 20:1220:12, 26 March 2010‎ Giftlite talk contribs‎ m 3,170 bytes +1‎ +: undo

20 March 2010

• curprev 19:0419:04, 20 March 2010‎ RobinK talk contribs‎ 3,169 bytes +596‎ added more info about STCON and clarified relationship with USTCON undo

5 December 2009

• curprev 12:5112:51, 5 December 2009‎ Miym talk contribs‎ m 2,573 bytes +2‎ →‎Complexity: caps, en-dash undo
• curprev 12:4812:48, 5 December 2009‎ Miym talk contribs‎ m 2,571 bytes +40‎ html math undo
• curprev 12:3112:31, 5 December 2009‎ Miym talk contribs‎ m 2,531 bytes +7‎ →‎Complexity: O(...) undo
• curprev 12:3012:30, 5 December 2009‎ Miym talk contribs‎ m 2,524 bytes +12‎ →‎Complexity: html math; number of nodes = n undo
• curprev 12:2512:25, 5 December 2009‎ Miym talk contribs‎ m 2,512 bytes −62‎ →‎See also: rm self-link undo
• curprev 05:4805:48, 5 December 2009‎ David Eppstein talk contribs‎ 2,574 bytes 0‎ rm what is now a self-link undo
• curprev 05:4705:47, 5 December 2009‎ David Eppstein talk contribs‎ 2,574 bytes +32‎ cat undo

23 August 2009

• curprev 03:0003:00, 23 August 2009‎ RobinK talk contribs‎ m 2,542 bytes −45‎ Removed category Computational complexity theory (using HotCat) undo

27 May 2009

• curprev 18:2718:27, 27 May 2009‎ Debresser talk contribs‎ m 2,587 bytes +4‎ minor undo

25 May 2009

• curprev 06:5306:53, 25 May 2009‎ Luisldq talk contribs‎ 2,583 bytes +41‎ →‎Complexity undo

14 December 2008

• curprev 15:2715:27, 14 December 2008‎ Citation bot talk contribs‎ m 2,542 bytes −10‎ Updating page numbers after recent improvement to Template:Cite book. Added: page. Formatted: pages. undo

22 October 2008

• curprev 15:3315:33, 22 October 2008‎ 70.179.91.2 talk‎ 2,552 bytes +29‎ restored category "directed graphs" undo
• curprev 15:3015:30, 22 October 2008‎ 128.100.5.116 talk‎ 2,523 bytes −85‎ reverting: "Connectivity is solvable in deterministic logspace.." is misleading since link refers to undirected problem undo

17 October 2008

• curprev 23:1123:11, 17 October 2008‎ Altenmann talk contribs‎ 2,608 bytes +29‎ Category:Directed graphs undo

3 September 2008

• curprev 19:5119:51, 3 September 2008‎ 128.100.3.41 talk‎ 2,579 bytes +56‎ No edit summary undo

18 April 2008

• curprev 16:3116:31, 18 April 2008‎ Chris-martin talk contribs‎ m 2,523 bytes −1‎ →‎Complexity: punctuation before ref tag undo

10 December 2007

• curprev 19:4819:48, 10 December 2007‎ 129.186.67.1 talk‎ 2,524 bytes −1‎ No edit summary undo

16 September 2007

• curprev 20:5020:50, 16 September 2007‎ PaulTanenbaum talk contribs‎ 2,525 bytes −72‎ Copyedited and added link to reachability undo

24 April 2007

• curprev 19:5919:59, 24 April 2007‎ Ihendley talk contribs‎ m 2,597 bytes +4‎ →‎Complexity undo

27 March 2007

• curprev 18:5318:53, 27 March 2007‎ Furby100 talk contribs‎ m 2,593 bytes 0‎ moved ST-connectivity to St-connectivity over redirect: This will make the title display correctly. undo
• curprev 18:5018:50, 27 March 2007‎ Furby100 talk contribs‎ 2,593 bytes −6‎ No edit summary undo

1 February 2007

• curprev 16:4716:47, 1 February 2007‎ Creidieki talk contribs‎ m 2,599 bytes +15‎ →‎References: fix the reference I just added (sorry, not very good at this.) undo
• curprev 16:4616:46, 1 February 2007‎ Creidieki talk contribs‎ m 2,584 bytes +1‎ →‎Complexity: fix ref undo
• curprev 16:4516:45, 1 February 2007‎ Creidieki talk contribs‎ 2,583 bytes +328‎ →‎Complexity: +complete for P on alternating graphs (w/ ref to Immerman 99) undo

13 November 2006

• curprev 00:4900:49, 13 November 2006‎ Creidieki talk contribs‎ 2,255 bytes +296‎ +complete for first-order reductions undo

14 August 2006

• curprev 20:0920:09, 14 August 2006‎ Duesentrieb talk contribs‎ 1,959 bytes +42‎ de:Erreichbarkeitsproblem in Graphen undo

17 April 2006

• curprev 04:2304:23, 17 April 2006‎ Troworld talk contribs‎ 1,917 bytes +5‎ →‎Complexity: link to NTM undo

6 April 2006

• curprev 16:4516:45, 6 April 2006‎ Brighterorange talk contribs‎ m 1,912 bytes −58‎ →‎Complexity: remove repetition undo

1 April 2006

• curprev 21:5221:52, 1 April 2006‎ Creidieki talk contribs‎ m 1,970 bytes +34‎ Category:NL-complete problems undo
• curprev 21:5221:52, 1 April 2006‎ Creidieki talk contribs‎ m 1,936 bytes 0‎ wk "NL-complete" undo

28 March 2006

• curprev 12:0012:00, 28 March 2006‎ That Guy, From That Show! talk contribs‎ 1,936 bytes −8‎ bad link repair. You can help! undo

26 February 2006

• curprev 12:2312:23, 26 February 2006‎ That Guy, From That Show! talk contribs‎ 1,944 bytes −5‎ migrate {{book reference}} to {{cite book}} using AWB undo