Editing Space hierarchy theorem (section)

=== Corollary 5 ===

:SPACE(''n'') ≠ [[PTIME]].

To see it, assume the contrary, thus any problem decided in space <math>O(n)</math> is decided in time <math>O(n^c)</math>, and any problem <math>L</math> decided in space  <math>O(n^b)</math> is decided in time <math>O((n^b)^c)=O(n^{bc})</math>. Now <math>\mathsf{P}:=\bigcup_{k\in\mathbb N}\mathsf{DTIME}(n^k)</math>, thus P is closed under such a change of bound, that is <math>\bigcup_{k\in\mathbb N}\mathsf{DTIME}(n^{bk})\subseteq\mathsf{P}</math>, so <math>L\in\mathsf{P}</math>. This implies that for all <math>b, \mathsf{SPACE}(n^b)\subseteq\mathsf{P}\subseteq\mathsf{SPACE}(n)</math>, but the space hierarchy theorem implies that <math>\mathsf{SPACE}(n^2)\not\subseteq\mathsf{SPACE}(n)</math>, and Corollary 6 follows. Note that this argument neither proves that <math>\mathsf{P}\not\subseteq\mathsf{SPACE}(n)</math> nor that <math>\mathsf{SPACE}(n)\not\subseteq\mathsf{P}</math>, as to reach a contradiction we used the negation of both sentences, that is we used both inclusions, and can only deduce that at least one fails. It is currently unknown which fail(s) but conjectured that both do, that is that <math>\mathsf{SPACE}(n)</math> and <math>\mathsf{P}</math> are incomparable -at least for deterministic space.<ref>{{cite web | url=https://mathoverflow.net/questions/40770/how-do-we-know-that-p-linspace-without-knowing-if-one-is-a-subset-of-the-othe/40771#40771 | title=How do we know that P != LINSPACE without knowing if one is a subset of the other? }}</ref> This question is related to that of the time complexity of (nondeterministic) [[linear bounded automata]] which accept the complexity class <math>\mathsf{NSPACE}(n)</math> (aka as [[context-sensitive languages]], CSL); so by the above CSL is not known to be decidable in polynomial time -see also [[Linear_bounded_automaton#LBA_problems|Kuroda's two problems on LBA]].