Space hierarchy theorem: 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 01:2801:28, 10 March 2025 Cosmia Nebula talk contribs 16,494 bytes +70 →Refinement of space hierarchy: nspace undo Tag: Visual edit
curprev 01:2801:28, 10 March 2025 Cosmia Nebula talk contribs 16,424 bytes −32 →Refinement of space hierarchy: clearer language undo Tag: Visual edit
curprev 01:1501:15, 10 March 2025 Cosmia Nebula talk contribs 16,456 bytes +26 g undo Tag: Visual edit
curprev 01:1401:14, 10 March 2025 Cosmia Nebula talk contribs 16,430 bytes +521 →Comparison and improvements: space cons undo Tag: Visual edit

curprev 09:0809:08, 17 December 2024 LicenceToCrenellate talk contribs 15,909 bytes −2 Spacing and linting fixes undo Tags: Mobile edit Mobile web edit Advanced mobile edit

curprev 22:4222:42, 21 December 2023 JT0202 talk contribs 15,911 bytes −287 Removed corollary 2 of real numbered argument space class differences undo

curprev 12:5412:54, 8 September 2023 Plm203 talk contribs 16,198 bytes +9 →Corollary 6: Actually it seems, after asking, that P is also conjectured to not be contained in NSPACE(n). undo
curprev 06:3706:37, 8 September 2023 Plm203 talk contribs 16,189 bytes +65 →Corollary 6: Added the precision that incomparability is only conjectured for DSPACE(n) -it seems that P (and even NP) is contained in NSPACE(n) undo

curprev 21:0921:09, 31 August 2023 Citation bot talk contribs 16,124 bytes +111 Add: title. Changed bare reference to CS1/2. | Use this bot. Report bugs. | Suggested by Abductive | Category:Theorems in computational complexity theory | #UCB_Category 19/21 undo

curprev 19:5119:51, 24 August 2023 Plm203 talk contribs 16,013 bytes +34 →Corollary 6: Clarified a double-negation undo

curprev 19:4519:45, 23 August 2023 Plm203 talk contribs 15,979 bytes +52 →Corollary 6 undo
curprev 19:0119:01, 23 August 2023 Plm203 talk contribs 15,927 bytes +1,630 →Corollaries undo

curprev 21:3521:35, 31 October 2022 Ndrwngb talk contribs 14,297 bytes +54 No edit summary undo

curprev 09:4809:48, 14 July 2022 Malku H₂n̥rés talk contribs 14,243 bytes −4 →Proof undo Tags: Mobile edit Mobile web edit

curprev 20:3420:34, 28 July 2021 Yuval Filmus talk contribs 14,420 bytes +27 →Proof: Switched k to math notation undo
curprev 19:2019:20, 28 July 2021 2001:b07:5d37:54c0:e5d5:8a7f:450c:c25f talk 14,393 bytes −2 →Proof undo
curprev 19:1919:19, 28 July 2021 2001:b07:5d37:54c0:e5d5:8a7f:450c:c25f talk 14,395 bytes +36 →Proof undo

curprev 17:1617:16, 13 January 2021 Monkbot talk contribs m 14,359 bytes +4 Task 18 (cosmetic): eval 4 templates: hyphenate params (4×); undo Tag: AWB

curprev 21:2721:27, 8 June 2020 ArnoldReinhold talk contribs 14,355 bytes +112 Adding local short description: "Both deterministic and nondeterministic machines can solve more problems given more space", overriding Wikidata description "theorem" (Shortdesc helper) undo

curprev 18:5618:56, 25 March 2020 Iridescent talk contribs m 14,243 bytes +3 Cleanup and typo fixing, typo(s) fixed: In other words → In other words,, 1-3 → 1–3 undo Tag: AWB

curprev 08:5908:59, 29 December 2019 CiaPan talk contribs 14,240 bytes +120 {{Cleanup}} undo

curprev 02:4702:47, 8 September 2019 InternetArchiveBot talk contribs 14,120 bytes +93 Bluelinking 1 books for verifiability.) #IABot (v2.1alpha3 undo

curprev 16:2016:20, 22 November 2018 Deansg talk contribs m 14,027 bytes +56 →Proof: Another small fix undo

curprev 15:4315:43, 21 November 2018 Deansg talk contribs 13,971 bytes +454 →Proof: Fix a few ambiguities in the proof and add a little more detail. undo

curprev 00:2100:21, 26 October 2017 81.107.169.80 talk 13,517 bytes −2 →Statement undo

curprev 05:0505:05, 18 September 2017 Dmytro talk contribs 13,519 bytes +482 →Refinement of space hierarchy: be more precise about when O(1)-space overhead is possible undo

curprev 10:5910:59, 18 March 2017 TheoreticalComputerScientist talk contribs 13,037 bytes +8 Added a link to Viliam Geffert intending to write an article about his work undo

curprev 04:2904:29, 29 September 2016 Cedar101 talk contribs 13,029 bytes +179 it has become popular in recent years to write the names of complexity classes in a sans serif font undo
curprev 02:5002:50, 29 September 2016 Cedar101 talk contribs 12,850 bytes −49 it has become popular in recent years to write the names of complexity classes in a sans serif font undo

curprev 05:3705:37, 24 August 2016 Yobot talk contribs m 12,899 bytes +8 clean up / fix section header naming (WP:ASL) using AWB (12082) undo

curprev 02:0502:05, 15 February 2016 Cedar101 talk contribs m 12,891 bytes −39 →Corollaries: \mathrm undo
curprev 02:0102:01, 15 February 2016 Cedar101 talk contribs m 12,930 bytes −10 →Corollary 4: : ⊊ undo
curprev 02:0102:01, 15 February 2016 Cedar101 talk contribs m 12,940 bytes −16 →Corollary 3: replace \subsetneq to ⊊, introduce \mathrm undo

curprev 08:5208:52, 27 October 2015 Jérôme talk contribs 12,956 bytes −9 →Comparison and improvements: remove peacock term "striking" undo

curprev 12:0512:05, 7 March 2015 Jochen Burghardt talk contribs 12,965 bytes +56 →top: wikilink little o undo

curprev 07:1707:17, 24 July 2014 77.126.203.44 talk 12,909 bytes 0 The contradictions were reversed. undo

curprev 20:2520:25, 7 April 2014 195.77.88.65 talk 12,909 bytes +45 See Also: Time hierarchy theorem undo

curprev 05:4405:44, 3 December 2013 69.165.245.200 talk 12,864 bytes +15 No edit summary undo
curprev 05:4305:43, 3 December 2013 69.165.245.200 talk 12,849 bytes −2 →Corollary 3 undo
curprev 05:4305:43, 3 December 2013 69.165.245.200 talk 12,851 bytes 0 →Corollary 3 undo
curprev 05:4205:42, 3 December 2013 69.165.245.200 talk 12,851 bytes +5 →Corollary 3 undo

curprev 21:5721:57, 19 November 2013 Algebran talk contribs 12,846 bytes −1 Undid revision 582433952 by Algebran (talk) undo
curprev 21:4721:47, 19 November 2013 Algebran talk contribs 12,847 bytes +1 Corrected definition of language undo

curprev 12:0512:05, 5 August 2013 2.14.76.78 talk 12,846 bytes +4 You have a problem with the word 'therefore' undo
curprev 12:0112:01, 5 August 2013 2.14.76.78 talk 12,842 bytes +1 Ortograf undo

10 March 2025

17 December 2024

21 December 2023

8 September 2023

31 August 2023

24 August 2023

23 August 2023

31 October 2022

14 July 2022

25 April 2022

28 July 2021

13 January 2021

8 June 2020

25 March 2020

29 December 2019

8 September 2019

22 November 2018

21 November 2018

26 October 2017

18 September 2017

18 March 2017

29 September 2016

24 August 2016

15 February 2016

27 October 2015

7 March 2015

24 July 2014

7 April 2014

3 December 2013

19 November 2013

5 August 2013