18. Logarithmic Space

By refining our basic space cost definition, we can study the complexity classes corresponding to languages that can be decided with a sublinear amount of space.

L and NL

The main modification we want to consider to the standard Turing machine model in order to study sublinear space complexity classes is to make the input tape read-only and add a new work tape that the Turing machine can use (in read/write fashion) as usual during its execution.

Definition. An input/work tape Turing machine is a two-tape Turing machine whose input is on the first read-only tape and where the other tape is a standard read/write tape that is initially empty.

Apart from the restriction that the first tape is read-only, input/work tape Turing machines behave exactly as standard Turing machines. The extension of verifiers to input/work tape verifiers is also done in the same way, with the certificate also being read-only (as before).

The space cost of an input/work tape Turing machine $M$ on input $x$ is the number of distinct cells in the work tapes that are accessed before $M$ halts. With this definition, we can now define worst-case space cost and the $\mathbf{SPACE}$ complexity classes as before in a way that now give non-trivial sublinear space complexity classes.

The classes $\mathbf{L}$ and $\mathbf{NL}$ represent the set of languages that can be decided efficiently in terms of both time and space complexity, as the following result shows.

Proposition. $\mathbf{L}\subseteq \mathbf{NL}\subseteq \mathbf{P}\subseteq \mathbf{NP}$.

Proof. This result is another direct corollary of the Time-Space Hierarchy theorem from the last lecture.

Are any of these inclusions strict? After all, it seems intuitively obvious that some languages in $\mathbf{P}$ should require more than a logarithmic amount of space to decide, but in fact even proving that $\mathbf{L}\ne \mathbf{NP}$ remains open.

NL-Completeness

Does $\mathbf{L}=\mathbf{NL}$? Savitch’s theorem shows that $\mathbf{NL}\subseteq \mathbf{SPACE}({\log }^{2}n)$, but this does not resolve the question. We can make progress on it by studying the class of languages which are complete for $\mathbf{NL}$. To define $\mathbf{NL}$-completeness, we first need to introduce a new type of reduction.

Definition. Given two languages $A,B\subseteq {\mathrm{\Sigma }}^{\ast }$, the language $A$ is log-space reducible to $B$, denoted

$$A{\le }_{\mathbf{L}}B$$

if there is a function $f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Sigma }}^{\ast }$ such that

1. For every $x\in {\mathrm{\Sigma }}^{\ast }$, we have $x\in A\iff f(x)\in B$; and

2. There is a logarithmic-space Turing machine $M$ that on input $x\in {\mathrm{\Sigma }}^{\ast }$, index $i\in \mathbb{N}$, and symbol $\sigma \in \mathrm{\Sigma }$, accepts if and only if the $i$th symbol of $f(x)$ is $\sigma$.

Remarks.

• As per the definition, when the index $i$ is larger than the length of the string $f(x)$, $M$ rejects on $(x,i,\sigma )$ for all values of $\sigma$.

• Whenever $A{\le }_{\mathbf{L}}B$, then $A{\le }_{\mathbf{P}}B$ also holds. That’s because by iterating $M$ on indices $i=1,2,\dots$ and all $\sigma \in \mathrm{\Sigma }$, we can compute $f(x)$ in polynomial time.

• However, the converse is not necessarily true: if $\mathbf{L}\ne \mathbf{P}$, then there are languages for which $A{\le }_{\mathbf{P}}B$ holds but $A{\le }_{\mathbf{L}}B$ does not.

Log-space reductions play the same role for $\mathbf{L}$ and $\mathbf{NL}$ as polynomial-time reductions played for $\mathbf{P}$ and $\mathbf{NP}$.

Lemma. For every two languages $A,B$ that satisfy $A{\le }_{\mathbf{L}}B$,

• If $B\in \mathbf{L}$, then $A\in \mathbf{L}$ as well; and

• If $B\in \mathbf{NL}$, then $A\in \mathbf{NL}$ as well.

Proof. Let $T$ be a machine that provides the logarithmic space reduction from $A$ to $B$.

Consider an input $x\in {\mathrm{\Sigma }}^{\ast }$. Ideally, we would like to use $T$ to output $f(x)$ on the tape and then invoke a (deterministic or non-deterministic) logspace TM $M$ for $B$ on input $f(x)$ to determine if $x\in A$ or not.

But the problem with this approach is that we can’t write $f(x)$ on the tape when we only have logarithmic space. So instead we simulate access to the input tape for $M$: we use a counter to keep track of the tape head position of $M$ on the input tape, and we use $T$ to determine what the symbol of $f(x)$ is at that position to simulate each transition of $M$. Doing so enables us to simulate $M$ accurately with only a logarithmic space extra cost.

We can now define the class of $\mathbf{NL}$-complete languages.

Definition. The language $L$ is $\mathbf{NL}$-complete if

1. Every language $A\in \mathbf{NL}$ satisfies $A{\le }_{\mathbf{L}}L$; and

2. $L\in \mathbf{NL}$.

By the last lemma, to show that $\mathbf{L}=\mathbf{NL}$, it suffices to show that any $\mathbf{NL}$-complete language is in $\mathbf{L}$. And, as it turns out, there are natural problems that correspond to $\mathbf{NL}$-complete languages.

Connectivity

The $(s,t)$-connectivity language we introduced in the last lecture plays a central role in the study of logarithmic space complexity. As a first observation, we can verify this language with a logarithmic amount of space.

Lemma. $\mathsf{\text{STCON}}\in \mathbf{NL}$.

Proof. Consider the verifier $V$ whose certificate represents a sequence of vertices in the graph that starts in $s$ and ends in $t$. $V$ can verify that each pair of adjacent vertices in the certificate are indeed connected by an edge in the graph and also that the length of the sequence includes at most $k$ vertices. Both these checks require only a logarithmic amount of space.

The language $\mathsf{\text{STCON}}$ is $\mathbf{NL}$-complete.

Theorem. $\mathsf{\text{STCON}}$ is $\mathbf{NL}$-complete.

Proof. We already saw that $\mathsf{\text{STCON}}\in \mathbf{NL}$ so it remains to show that it is $\mathbf{NL}$-hard.

Fix any language $L\in \mathbf{NL}$. Let $V$ be a verifier that decides $L$ with space cost $O(\log n)$.

Let us consider partial configurations of $V$. Such partial configuration is defined by the current state of $V$, the position of its tape heads on the input, certificate, and work tapes, and the contents of the input and work tapes. Importantly, a partial configuration of $V$ does not include the content of the certificate tape.

Define $G$ to be the partial configuration graph of $V$, as defined in the last lecture. Each partial configuration of $V$ is a vertex, and there is a directed edge from $c_1$ to $c_2$ when there is a certificate that causes $V$ to go from configuration $c_1$ to $c_2$ in one step. We can assume without loss of generality that $V$ has a single accepting configuration $c_{\mathbf{A}}$.

When $V$ has space cost $O(\log n)$, the number of partial configurations of the machine is polynomial in $n$. And the transformation from $V$ to $G$ can be completed with logarithmic space cost. Finally, there is a parameter $k$ such that an input $x$ is in $L$ if and only if $(G,c_x,c_{\mathbf{A}},n^k)\in \mathsf{\text{STCON}}$ where $c_x$ is the vertex corresponding to the initial configuration of $G$ on input $x$. This means that we obtain the logspace reduction $L{\le }_{\mathbf{L}}\mathsf{\text{STCON}}$.

This last result shows that we can resolve the $\mathbf{L}$ vs. $\mathbf{NL}$ question simply by determining whether connectivity can be solved with logarithmic space or not.