Computational Complexity HT25, Sublinear space classes

\[\mathsf{L} = \mathsf{DSPACE}(\log n)\]

\[\mathsf{NL} = \mathsf{NSPACE}(\log n)\]

A log-space transducer is a Turing machine $M$ where

• It has multiple tapes:
  • A read-only input tape
  • A write-only output tape
  • One or more read-write work tapes
• The work tape can use at most $O(\log n)$ cells
• $M$ computes a function $f : \Sigma^\ast \to \Sigma^\ast$

Any such $f$ computable this way is called a log-space computable function.

$A$ is mapping reducible to $B$ by means of a log space computable function $f$.

$B \in \mathsf{NL}$ and every language $A \in \mathsf{NL}$ is log-space reducible to $B$.

Let $M _ B$ be the log-space Turing machine deciding $B$. We construct a Turing machine $M _ A$ which decides whether $w \in A$ as follows:

• $M _ A(w)$:
  • Simulates $M _ B$ on $f(w)$.
  • Since $f(w)$ can’t be stored directly since it might be too large, so every time $M _ B$ needs to read the cell that would correspond to the $i$-th cell of $f(w)$, $M _ A$ restarts the computation of $f(w)$ and ignores all output except for the desired location of $f(w)$.

Note that if $A \le _ L B$ and $B \in L$, then $A \in L$.

Since $\mathsf{NL} \subseteq \mathsf{P}$, all problems in $\mathsf{NL}$ are solvable in polynomial time. Therefore any two languages in $\mathsf{NL}$ except $\emptyset$ and $\Sigma^\ast$ are polynomial time reducible to one another.

For example, pick $A, B \in \mathsf{NL} \setminus \{\emptyset, \Sigma^\ast\}$. Then $A \le _ m^\text{poly} B$ since for any $w \in \{0, 1\}^\ast$, it’s possible to compute in polynomial time the following function:

\[f(w) = \begin{cases} b &\text{if } w \in A \\\\ \overline b &\text{otherwise} \end{cases}\]

where $b \in B$ and $\overline b \notin B$. Then $f(w) \in B$ iff $w \in A$.

Using the fact that $\mathsf{NL} = \mathsf{coNL}$, so showing it belongs to the opposite class instead.

Guess a sequence of vertices

\[v_0 = s, v_1, \ldots, v_k\]

where $k \le n$. At stage $i$, maintain only $i$ in memory with vertices $v _ {i-1}$ and $v _ i$.

Check that $i \le n$ and that there is an edge from $v _ {i-1}$ to $v _ i$.

If either of the conditions fail, reject. Otherwise, check whether $v _ i = t$ and accept if so, or increment $i$.

\[\mathsf{PATH} = \\{ \langle G, s, t \rangle \mid \text{path from }s\text{ to }t\text{ in }G \\}\]

• $\mathsf{PATH}$ is $\mathsf{NL}$-complete
• Hence $\overline{\mathsf{PATH} }$ is $\mathsf{coNL}$-complete
• $\overline{\mathsf{PATH} } \in \mathsf{NL}$ by a clever algorithm
• Hence $\mathsf{NL} = \mathsf{coNL}$.

Fix some language $L$ with corresponding logspace NTM $N$.

Overall idea: Construct a graph whose nodes are configurations of $N$ and edges represent possible computational steps of $\mathcal M$ on $w$. Then find a path from the start configuration to an accepting configuration.

---

Construct $\langle G, s, t \rangle$ from $\mathcal M$ using a $\mathsf{LOGSPACE}$-transducer:

• A configuration $(q, x _ 1, \ldots, x _ n, p _ \text{input}, p _ 1 \ldots, p _ n)$ of $\mathcal M$ on $w$ can be described in $c \log n$ space for some constant $c$ and $n = \vert w \vert $ (since the input tape is read-only, we don’t have to store the input explicitly and can instead leave it implicit in the representation)
• List the nodes of by iterating through all strings of length $c \log n$ and outputting those corresponding to legal configurations.
• List the edges of $G$ by going through all pairs of strings $(C _ 1, C _ 2)$ of length $c \log n$ and outputting pairs where $C _ 1 \vdash _ {\mathcal M} C _ 2$.
• Take $s$ to be the starting configuration, and we may assume without loss of generality that $\mathcal M$ has a single accepting configuration $t$.

Then $w \in L$ iff $\langle G, s, t \rangle \in \mathsf{PATH}$.

Note that $\mathsf{PATH}$ is $\mathsf{NL}$-complete with respect to log-space $m$-reductions, and also that $\mathsf{PATH}$ is decidable is polynomial time.

Since a Turing machine that uses space $f(n)$ runs in time $2^{O(f(n))}$, it follows that a log-space reducer using log-space also runs in polynomial time.

Hence any language in $\mathsf{NL}$ is polynomial time reducible to $\mathsf{PATH}$, which can be decided in polynomial time.

---

If you don’t have to consider $\mathsf{PATH}$, you could use the result which says

\[\mathsf{NSPACE}(S) \subseteq \mathsf{DTIME}(2^{O(S)})\]

and take $S$ to be $\log n$.

$\mathsf{SCOP}$ is in $\mathsf{NL}$:

• Loop over all pairs of vertices $u, v \in G$
  • Guess $w$ and connecting paths between $u$ and $v$ that use $w$
• Accept if there is a path for each pair passing through $w$
• Can be done in logarithmic space

---

$\mathsf{SCOP}$ is $\mathsf{NL}$-hard:

Given $\langle G, a, b \rangle$, construct $G’$ as follows:

• Loop through all vertices of $G$, keep all but replace $a$ and $b$ with $a, a’, a’’$ and $b, b’, b’’$.
• Add all edges between $a, a’, a’’$ and also all edges between $b, b’, b’’$.
• Loop through edges of $G$ and keep each edge $\langle v, w\rangle$
• Loop through vertices $v \in G$. If $v \ne a$, then output all edges from $v$ to $a, a’, a’’$, similarly if $v \ne b$, then output all edges from $b, b’, b’’$ to $v$

If $G$ has a directed path from $a$ to $b$, then $G’$ is in $\mathsf{SCOP}$ as for any two nodes $x$ and $y$ there are paths $xaby$ and $yabx$, and these can be modified to both contain $a’$.

If $G$ contains $(a, b)$, then there are paths from $a$ to $b$ and back, both containing $a’$, and likewise for all other pairs of vertices such as $a’$ and $b’’$.

@example~ @exam~