# $\mathbf{NC_2}$ is closed under log-space reduction

I actually have to prove the following :

$\mathbf{NL} \subseteq \mathbf{NC_2}$

I have the following approach :

1. I will prove that $\mathbf{PATH} = \{〈D, s, t〉 | \text{D is a directed graph with a path from vertex s to t}\} \in \mathbf{NC_2}$.

2. I will show that $\mathbf{NC_2}$ is closed under log-space reductions i.e:

$$(1): B \in \mathbf{NC_2} \hbox{ and } A \le_l B \Longrightarrow A \in \mathbf{NC_2}$$

where $\le_l$ is the logspace reduction defined as

$$A \le_l B :\Longleftrightarrow (\exists M \hbox{ TM}, \forall x)[x \in A \Longleftrightarrow M(x) \in B]$$

($M$ is a TM which runs in logarithmic space).

1. Since $\mathbf{PATH}$ is an $\mathbf{NL}$-complete problem the proof will be done.

Proving The 1st part was easy, i am stuck at the second part and have no idea how to proceed.

Any help?

• What uniformity condition do you impose? ​ ​
– user12859
Nov 5 '15 at 15:04
• Log-space uniformity! Nov 5 '15 at 15:13
• Do you have to use the approach described in your question? ​ ​
– user12859
Nov 5 '15 at 15:22
• Yes, i have seen another approach and i want to know if i can do it using mine. Nov 5 '15 at 15:23
• The circuit should presumably solve a polynomial number of logspace problems to find M(x). $\:$ (Also, if you've gotten to the point of asking about a different proof strategy, then you might also want to strengthen it to show that NL is a subset of Dlogtime-uniform AC$_1$.) $\;\;\;\;$
– user12859
Nov 5 '15 at 15:30

We want to show that if $A\le_lB$ and $B\in NC_2$ then $A\in NC_2$.
Since $A\le_l B$ we have a Turing machine $M_{f,i}(x)$ calculating the i'th bit of the reduction output $f(x)_i$, using logarithmic space.
$M_{f,i}(x)=1 \iff \left( G_{M_{f,i}(x)},c_{start},c_{acc} \right)\in PATH$
Where $G_{M_{f,i}(x)}$ is the configuration graph of the computation of the logspace machine $M_{f,i}$ on $x$,and $c_{start},c_{acc}$ are the initial and accepting configurations, correspondingly.
Now your $NC_2$ circuit for $A$ will, "in parallel", compute all the bits of the reduction $f(x)$ (this can be done since you proved $PATH\in NC_2$) and send the result as input to the $NC_2$ circuit for $B$. This results in an $NC_2$ circuit for $A$.
• I wanted to talk about strictly logspace machines, and not ones who allow polynomial output tape. This also allows me to formulate the problem of computing $f(x)$ as inputs to $PATH$, since any bit of $f(x)$ is either 0 or 1, we can formulate this as a decision problem and talk about the usual configurations graph. Nov 5 '15 at 19:50