---
title: "Space Complexity"
type: concept
related: [Space Class L, Space Complexity]
source: https://www.jemoka.com/posts/kbhspace_complexity/
confidence: high
status: active
---

We define Space Complexity as the largest tape index reached during computation.
Let \(M\) be a deterministic Turing Machine; the space complexity of \(M\) is the function \(S: \mathbb{N} \to \mathbb{N}\), where \(S(n)\) is the largest number of work tape cells accessed by \(M\) on \(X\); we will consider the input tape as read-only but also it is free (because if we didn&rsquo;t do this, our space complexity would be trivially \(\geq n\) and that&rsquo;s kinda lame).
\begin{equation} \text{SPACE}\qty(S(n)) = \qty {A \mid A \text{ is decidable by TM with $O(S(n))$ space}} \end{equation}
these classes involve computations with bounded memory
constituents requirements additional information L See Space Class L
upper-bounding space complexity with time complexity \begin{equation} \text{TIME}\qty(t\qty(n)) \subseteq \text{SPACE}\qty(t\qty(n)) \end{equation}
If a TM runs in time \(\leq t\), it can only touch \(\leq t\) cells.
\(P \subseteq \text{PSPACE}\) \(\text{NP} \subseteq \text{PSPACE}\) upper-bounding time complexity with space complexity \begin{equation} \text{SPACE} \qty(s \qty(n)) \subseteq \text{TIME}\qty(2^{O\qty(s\qty(n))}) \end{equation}
For \(L \in \text{SPACE}\qty(S(n))\), what is its upper-bounded time complexity? Consider the number of configurations of our system:
work tape contents (content of each tape slot): \(2^{O\qty(\sqrt{n})}\) current state: \(O(1)\) worktape head: \(O\qty(s\qty(n))\) input tape haed position: \(O\qty(n)\) assuming \(S\qty(n) \geq \log n\) (which gives us \(O \qty(n) \cdot 2^{O(s\qty({n}))} = 2^{O\qty(s \qty(n))}\)), we have that there is only \(2^{O \qty(s \qty(n))}\) configurations.
Observe: since \(M\) never loops, no configuration appears twice. Hence, the runtime of \(m\) must be smaller than the number of distinct configurations.
PSPACE let
\begin{equation} \text{PSPACE} = \bigcup_{k \in \mathbb{N}} \text{SPACE} \qty(n^{k}) \end{equation}
and recall
\begin{equation} \text{EXPTIME} = \bigcup_{k \in \mathbb{N}} \text{TIME} \qty(2^{n^{k}}) \end{equation}
then we can write:
\begin{equation} \text{PSPACE} \subseteq \text{EXPTIME} \end{equation}
because of the upper-bounding enlargement above
P, NP is in PSPACE \begin{equation} P \subseteq \text{PSPACE} \end{equation}
this is because the space is bounded by time&mdash;because if all you did was to go right, you will still do so by polynomial space
\begin{equation} NP \subseteq \text{PSPACE} \end{equation}
because you can use the same space to enumerate each of your choices
\begin{equation} NP^{NP} \subseteq \text{PSPACE} \end{equation}
Because the algorithm only takes \(PSPACE\) (since its \(NP\)), and the Oracle can be simulated out in \(PSPACE\)
hierarchy of space and time \begin{equation} \text{P} \subseteq \text{NP} \subseteq \text{PSPACE} \subseteq \text{EXPTIME} \end{equation}
Notice that \(P \neq \text{EXPTIME}\), because of the time hierarchy theorem&mdash;more time buys you more things to solve.
space hierarchy theorem \begin{equation} \text{SPACE}\qty(s(n)) \not \subseteq \text{SPACE}\qty(S(n)) \end{equation}
if \(\frac{s(n)}{S(n)} \to 0\) (i.e. \(S(n)\) is asymptotically larger than \(s(n)\))
argument sketch: nationalization; make a machine \(M\) which uses \(S(n)\) and does the opposite of every \(s(n)\) space machines on at least one input.
Note that \(L(M)\) is in \(\text{SPACE}\qty(S(n))\) but not \(\text{SPACE}\qty(s(n))\), because if it was it would&rsquo;ve then had a contradiction
nondeterministic space classes Let \(N\) be a nondeterministic Turing machine which halts on all inputs in all possible branches. The space complexity of \(N\) is function \(f\) where \(f(n)\) is the furthest tape cell reached by all computation paths, over all inputs of length \(n\).
\begin{equation} \text{NSPACE}\qty(s(n)) = \qty {L \mid \text{all things decided using $O(s(n))$ space complexity with a non-deterministic TM}} \end{equation}
examples \begin{equation} \text{3SAT} \in \text{SPACE}\qty(n) \end{equation}
Because we can try all assignments of \(n\) variables by length \(n\), this is in exponential time, but trying each only requires you to write down assignments of each which is in \(O(n)\).
\begin{equation} \text{NTIME}\qty(t(n)) \in \text{SPACE}(t(n)) \end{equation}
because the witness is at most \(t(n)\) (or at least you can truncate it as such since checking it only takes \(t(n)\) steps), and you need at most some factor against \(t(n)\) to check.
space complexity is tricky&hellip; We cannot reuse time, but we can reuse space. There are many, many counter-intuitive results.
Also, there are many counter-intuitive results: we will resolve space analogues \(\text{P} =^{?} \text{NP}\) and \(\text{NP} =^{?} \text{coNP}\) (in fact, in the opposite direction as expected!)
