Notes - Computational Complexity HT25, Sublinear space classes
Flashcards
@Define the class $\mathsf{L}$, aka $\mathsf{LOGSPACE}$.
@Define the class $\mathsf{NL}$, aka $\mathsf{NLOGSPACE}$.
@Prove that the directed graph reachability problem which asks if there is a path from vertex $s$ to vertex $t$ in a directed graph $G$ is in $\mathsf{NLOGSPACE}$.
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{NL}$ completeness
@Define a log-space transducer and a log-space computable function.
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.
@Define what it means for a language $A$ to be be log-space reducible to a language $B$, written $A \le _ L B$.
$A$ is mapping reducible to $B$ by means of a log space computable function $f$.
@Define what it means for a language $B$ to be $\mathsf{NL}$-complete.
$B \in \mathsf{NL}$ and every language $A \in \mathsf{NL}$ is log-space reducible to a $B$.
@Prove that if $A \le _ L B$ and $B \in L$, then $A \in L$.
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)$.
@Justify that if any $\mathsf{NL}$-complete language $B$ is in $\mathsf L$, $\mathsf{L} = \mathsf{NL}$.
Note that if $A \le _ L B$ and $B \in L$, then $A \in L$.
By appealing to results about $\mathsf{PATH}$, @prove that $\mathsf{NL} \subseteq \mathsf P$.
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$.
@Justify why it makes sense to define $\mathsf{NL}$-completeness in terms of logarithmic space $m$-reductions rather than polynomial time $m$-reductions.
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$.