Space Complexity

Relevant to this is time complexity and more generally decidability

Space complexity shares many of the features of time complexity and serves as an additional dimension with which to classify problems

Definition: The space complexity of a deterministic Turing machine $M$ that halts on all inputs is the function $f:\mathcal{N}\to \mathcal{N}$, where $f(n)$ is the maximum number of tape cells that $M$ scans on any input of length $n$

We say $M$ runs in space $f(n)$

If $M$ is a nondeterministic Turing machine, we define its space complexity $f(n)$ to be the maximum number of tape cells that $M$ scans on any branch

Definition: We define space complexity classes $\text{SPACE}(f(n))$ as the set of languages decided by an $O(f(n))$ space deterministic Turing machine and $\text{NSPACE}(f(n))$ as the set of languages decided by an $O(f(n))$ space nondeterministic Turing machine

Space is more powerful than space because it can be reused

For example, we can reason that $SAT$ can be reasonably solved in linear space, even though it’s an $\text{NP}$-complete problem

An important example we will look at is $AL{L}_{\text{NFA}}=\{⟨A⟩\mid A\text{ is an }\text{NFA and }L(A)={\Sigma }^{\ast }\}$

We can decide the complement $\overline{AL{L}_{\text{NFA}}}$ in linear space by nondeterministically reading in $2^q$ inputs (this is the maximum before it will repeat) and updating the possible states of our NFA accordingly

Savitch’s Theorem: For any $f(n)\ge n$, $\text{NSPACE}(f(n))\subseteq \text{SPACE}(f^2(n))$

Our regular way of simulating an NTM is not sufficient, because it could potentially use $2^{O(f(n))}$ space

So how does one prove this? Let $N$ decide $A$ nondeterministically in space $f(n)$

We construct a deterministic TM $M$ deciding $A$ using the procedure $\text{CANYIELD}$, which tests whether a configuration of $N$ can yield another within a specified number of steps

$\text{CANYIELD}(c_1,c_2,t)$ works by recursively checking for each $c_m$ using space $f(n)$ whether $\text{CANYIELD}\left(c_1,c_m,\frac{t}{2}\right)$ and $\text{CANYIELD}\left(c_m,c_2,\frac{t}{2}\right)$

We modify $N$ to clear the tape on accept and move the head to the leftmost cell, so that there is a single accept state, and select a constant $d$ such that $N$ has no more than $2^{df(n)}$ configurations using $f(n)$ tape

$M=$ “On input $w$: Output the result of $\text{CANYIELD}(c_{\text{start}},c_{\text{accept}},2^{df(n)})$”

This is correct, but how much space does our $\text{CANYIELD}$ method use? Well each level of the recursive stack must store $c_1,c_2,t$ which takes $O(f(n))$ space, and there are $O(\log 2^{df(n)})=O(f(n))$ levels, coming out to $O(f^2(n))$

(A technical difficulty is that this requires $M$ knowing the value of $f(n)$, but we can actually determine this manually by simulating on each value until we know it has rejected, and this is fine from a space standpoint)

Definition: $\text{PSPACE}$ is the class of languages decidable in polynomial space on a deterministic Turing machine, $\text{PSPACE}=\bigcup _k\text{SPACE}(n^k)$

We can also define $\text{NPSPACE}$, but as we showed $\text{PSPACE}=\text{NPSPACE}$

So by Savitch’s theorem, since $AL{L}_{\text{NFA}}$ is in $\text{coNSPACE}(n)$ we know it is also in $\text{PSPACE}$

We can easily reason $P\subseteq \text{PSPACE}$ and $\text{NP}\subseteq \text{NPSPACE}=\text{PSPACE}$

Similarly, a TM that uses $f(n)$ space cannot have more than $f(n)2^{O(f(n))}$ configurations before repeats, so $\text{PSPACE}\subseteq \text{EXPTIME}={\bigcup }_k^{}\text{TIME}(2^{n^k})$

In summary,
$\text{P}\subseteq \text{NP}\subseteq \text{PSPACE}=\text{NPSPACE}\subseteq \text{EXPTIME}$

Of these, the only certainty is $\text{P}\ne \text{EXPTIME}$, but general consensus is that these containments are all proper

PSPACE-Completeness

$\text{PSPACE}$ has an analog to NP-Completeness

Definition: A language $B$ is PSPACE-complete if $B$ is in $\text{PSPACE}$ and every $A$ in $\text{PSPACE}$ is polynomial time reducible to $B$

If $B$ is not necessarily in $\text{PSPACE}$ then we call it PSPACE-hard

The reason we use time reducibility instead of space reducibility is simply because time is much more limiting and a better representation of what we aim to achieve with completeness

To give an example, we introduce a more general type of Boolean formula which uses quantifiers in prenex normal form, known as quantified Boolean formulas (like $\varphi =\forall x\exists y[(x\vee y)\wedge (\bar{x}\vee \bar{y})]$)

When each variable is within the scope of a quantifier, the formula is fully quantified, sometimes called a sentence

$TQBF=\{⟨\varphi ⟩\mid \varphi \text{ is a true fully quantified Boolean formula}\}$

Theorem: $TQBF$ is $\text{PSPACE}$-complete

We can’t use the exact same method as with the Cook-Levin theorem, since the height of the tableau would be exponential and therefore cannot be produced in polynomial time

Instead, we use a technique related to our Savitch’s theorem proof

First, it’s apparent that we can specify a $\text{PSPACE}$ algorithm that decides $TQBF$

Now let $A$ be a language decided by a TM $M$ in space $n^k$ for some constant $k$

For our reduction, we design a formula parameterized as ${\varphi }_{c_1,c_2,t}$ where $\varphi$ is true if $M$ can go from $c_1$ to $c_2$ in at most $t$ steps (for convenience a power of $2$), and then our final reduction uses ${\varphi }_{c_{\text{start}},c_{\text{accept}},h}$ where $h=2^{df(n)}$ for a constant $d$

Like before, we define ${\varphi }_{c_1,c_2,t}$ to encode that either $c_1=c_2$ or $c_2$ follows from $c_1$ in a single step of $M$, using the same ideas as in the Cook-Levin theorem

For $t>1$, we construct ${\varphi }_{c_1,c_2,t}$ recursively

A naive approach might try ${\varphi }_{c_1,c_2,t}=\exists m_1\left[{\varphi }_{c_1,m_1,\frac{t}{2}}\wedge {\varphi }_{m_1,c_2,\frac{t}{2}}\right]$, but this still gives an exponentially large formula

A working recursive definition that reduces the size is ${\varphi }_{c_1,c_2,t}=\exists m_1\forall (c_3,c_4)\in \{(c_1,m_1),(m_1,c_2)\}\left[{\varphi }_{c_3,c_4,\frac{t}{2}}\right]$

This is possible because we can define $\forall (c_3,c_4)\in \{\dots \}$ in terms of Boolean operators, and so this definition properly adds $O(f(n))$ space for each division of $t$, yielding a formula of size $O(f^2(n))$

PSPACE-Complete Problems

A game is loosely defined as a competition in which opposing parties attempt to achieve some goal according to prespecified rules

Games are closely related to quantifiers, which we will demonstrate with an artificial formula game

Let $\varphi$ be some quantified Boolean formula in prenex normal form

Two players take turns selecting the values of the variables $x_1,\dots ,x_k$; Player A selects values bound to $\forall$ quantifiers and Player E selects values bound to $\exists$ quantifiers

Player A wins if $\psi$, the part of the formula without the quantifiers, is false, and Player E wins if it is true

We say that a player has a winning strategy for a game if that player can always win the game

$FORMULA\text{-}GAME=\{⟨\varphi ⟩\mid$ Player $E$ has a winning strategy in the formula game associated with $\varphi \}$

Theorem: $FORMULA\text{-}GAME$ is PSPACE-complete

This is clearly true because Player E wins precisely if $\varphi \in TQBF$, that is the process of choosing variables in order is exactly the condition under which a quantified variable is true or not

Let’s look at another kind of game based on geography, the children’s game in which players take turns naming cities that begin with the last letter of the previous city, until there are no option available

In generalized geography, we take an arbitrary directed graph with a designated start node

$GG=\{⟨G,b⟩\mid$ Player I has a winning strategy for the generalized geography game played on graph $G$ starting at node $b\}$

Theorem: $GG$ is PSPACE-complete

First, we can solve $GG$ with a recursive brute-force algorithm, which only requires the space of the recursion stack, i.e. linear space

To map the formula game to $GG$, we use a diamond construction somewhat reminiscent of the proof of HAMPATH’s NP-completeness, but much simpler

We first map $\varphi$ to a formula whose quantifiers start and end with $\exists$ and strictly alternate between $\exists$ and $\forall$, which we can easily do with dummy variables

Then, the geography game that simulates $\varphi$ goes in two parts

1. Players alternate selecting edges that represent the values of $x_1,\dots ,x_k$
2. Player A chooses a clause, and then Player E wins if they can choose a satisfied variable

In other words, no polynomial time algorithm exists for optimal play in generalized geography unless $\text{P}=\text{PSPACE}$, which is even stronger than $\text{P}=\text{NP}$

It would be nice if our methods could be applied to games like chess, however conventional board games have a finite state space and are thus unsuitable for asymptotic analysis

The Classes L and NL

If we modify our computational model slightly, we can meaningfully consider sublinear space bounds

We consider a two-tape model, where one tape is limited to the size of the input and is read only

With this model, we can exclude the size of the input from our space analyses

Definition: $\mathbf{L}=\text{SPACE}(\log n)$ is the class of languages that are decidable in logarithmic space on a deterministic Turing machine

Definition: $\mathbf{NL}=\text{NSPACE}(\log n)$ is the class of languages that are decidable in logarithmic space on a nondeterministic Turing machine

We consider logarithmic space because it is much smaller than linear but still solves useful problems, and happens to be robust under machine model and input encoding changes

One way of understanding the power of logarithmic space is with indices/pointers, which are logarithmic on the input size

Example: $A=\{0^k{1}^k\mid k\ge 0\}$
We can’t use our zig-zag approach, crossing off 0s and 1s, since that requires $O(n)$ space

Instead, we run through the input and use two binary counters to keep track of the number of 0s and 1s, and compare the counters at the end

In binary, each counter uses only logarithmic space, so this algorithm runs in $O(\log n)$ space, and $A\in \text{L}$

This is a very intuitive algorithm, but using counters is quite difficult to demonstrate explicitly in the Turing machine model

Example: PATH
We can solve this in $O(\log n)$ by only keeping track of the current node, and nondeterministically moving to the next one, until we either find the target or use $m$ steps

So $PATH$ is in $\text{NL}$

Our earlier claim that $f(n)$ space bounded Turing machines also run in time $2^{O(f(n))}$ is no longer true for very small space bounds, because our definitions have changed

We can analyze sublinear spaces with an updated definition of machine configurations

Definition: If $M$ is a Turing machine that has a separate read-only input tape and $w$ is an input, a configuration of M on w is a setting of the state, the work tape, and the positions of the two tape heads, but not the input $w$

If $M$ runs in $f(n)$ space and $w$ is an input of length $n$, the number of configurations of $M$ on $w$ is $n{2}^{O(f(n))}$, since each configuration stores the working tape and the location of the pointer on the read-only tape

So our bound accounting for sublinear spaces is $n{2}^{O(f(n))}$

Similarly, we can slightly modify the proof of Savitch’s Theorem to account for the updated definition, and the result is the same

NL-Completeness

Surprise! $\text{NL}$ also has an analogue to NP-Completeness

Everything is about the same, however since all $\text{NL}$ problems are solvable in polynomial time, we use a new kind of reducibility

Definition: A log space transducer is a Turing machine with a read-only input tape, a write-only output tape, and a read/write work tape, where the output tape cannot move leftward, and the work tape may contain $O(\log n)$ symbols

A log space transducer $M$ computes a log space computable function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ where $f(w)$ is the string remaining on the output tape after $M$ halts when it is started with $w$ on its input tape

Language $A$ is log space reducible to language $B$, written $A{\le }_{\text{L}}B$, if $A$ is mapping reducible to $B$ by means of a log space computable function $f$

Definition: A language $B$ is NL-complete if $B\in \text{NL}$ and every $A$ in $\text{NL}$ is log space reducible to $B$

Theorem: If $A{\le }_{\text{L}}B$ and $B\in \text{L}$, then $A\in \text{L}$

A naive approach would be directly mapping $w$ to $f(w)$, however $f(w)$ could be too large for the log-space bound

Instead, we trade time for space and recompute from scratch individual symbols whenever requested, such that only a single symbol of $f(w)$ needs to be stored at any point

Corollary: If any $\text{NL}$-complete language is in $\text{L}$, then $\text{L}=\text{NL}$

Theorem: $PATH$ is $\text{NL}$-complete

We map a log space Turing machine $M$ to a graph $G$, where the nodes represent configurations of $M$ on $w$, with an edge from $c_1$ to $c_2$ if $c_2$ is a possible next configuration of $M$ starting from $c_1$

We modify $M$ to have a unique accepting configuration, designated as $t$

This machine can operate in log space by sequentially going through all possible strings of length $c\log n$ and outputting them if valid configurations, and likewise for edges

Corollary: $\text{NL}\subseteq \text{P}$

This follows simply from the fact that a Turing machine using $f(n)$ space runs in $n{2}^{O(f(n))}$, so log space reducers run in polynomial time, and therefore every language in $\text{NL}$ is polynomial time reducible to $PATH$, which is in $\text{P}$

Log space reducibility is actually adequate for most reductions, and it terms out is enough for reductions like the $\text{PSPACE}$ reduction to $TQBF$, which can be useful in understanding relationships like $\text{NL}⊊\text{PSPACE}$

NL Equals coNL

$\text{NP}$ and $\text{coNP}$ are generally believed to be different, and our intuition would expect this fact to carry over to $\text{NL}$

Theorem: $\text{NL}=\text{coNL}$

The essence of the proof is showing that $\overline{PATH}$ is in $\text{NL}$, and therefore the rest of $\text{coNL}$

While this algorithm is not tricky to verify, I personally found the nondeterministic reasoning used to construct it tricky to fully grasp

We first calculate $c$, the number of nodes reachable from $s$
This cannot be done directly in logarithmic space, however we can use an iterative method

We calculate $c_{i+1}$ from $c_i$ by going through all nodes $v$ of $G$ and checking if any node reachable in $i$ steps has an edge to $v$

How do we make sure we’ve checked every node reachable in $i$ steps? Nondeterminism doesn’t help us for this, and we can’t just store the nodes reachable in $i$ because of the space constraint

We solve this by nondeterministically selecting a path to every node in $u$, and incrementing an auxiliary variable $d$
If we find $v$ then great, but otherwise we check if $d=c_i$ and reject otherwise

Now that we have our value $c$, we can nondeterministically select paths to each node (excluding $t$) and accept only if we reach $c$ nodes

Since we exclude $t$ from this search, reaching $c$ nodes means $t$ is not reachable, which concludes the algorithm

Since we only use counter variables, this algorithm runs in logarithmic space, and therefore $\text{NL}=\text{coNL}$

Our present knowledge of the relationships among complexity classes is $\text{L}\subseteq \text{NL}=\text{coNL}\subseteq \text{P}\subseteq \text{NP}⊊\text{PSPACE}$

The strict subset of $\text{NP}$ in $\text{PSPACE}$ is shown here

Most researchers conjecture that all these containments are proper, but we do not have the tools to prove much about it