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

Question

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).

3. 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?

• user12859: What uniformity condition do you impose? ​ ​
• Vikash Balasubramanian: Log-space uniformity!
• user12859: Do you have to use the approach described in your question? ​ ​
• Vikash Balasubramanian: Yes, i have seen another approach and i want to know if i can do it using mine.
• user12859: 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$.) $\;\;\;\;$

Answer 1

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$.

• Vikash Balasubramanian: Why do we require the subscript i in f(x) can't the transducer directly compute the entire output f(x)?
• Ariel: 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.