I actually have to prove the following :
$\mathbf{NL} \subseteq \mathbf{NC_2}$
I have the following approach :
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}$.
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).
- 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?