[Solved]: $\mathbf{NC}$ is closed under logspace reductions

Problem Detail: 

I am trying to solve the question 6.12 in Arora-Barak (Computational Complexity: A modern approach). The question asks you to show that the $\mathsf{PATH}$ problem (decide whether a graph $G$ has a path from a given node $s$ to another given node $t$) which is complete for $\mathbf{NL}$ is also contained in $\mathbf{NC}$ (this is easy). The question then also makes a remark that this implies that $\mathbf{NL} \subseteq \mathbf{NC}$ which is not obvious to me.

I think in order to show this, one has to show that $\mathbf{NC}$ is closed under logspace reductions, i.e

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

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

I would appreciate if someone could give a tip for proving the statement $(1)$.

Asked By : buckv

Answered By : Yuval Filmus

Given any language $L$ in NL decided by some machine $T$, you can decide whether $x \in L$ by considering the configuration graph of $T$ when run on $x$. This is why PATH is NL-complete. Given any length $n$ of the input, the configuration graph is a fixed polynomial-size graph which doesn't depend on $x$. Only the starting vertex depends on $x$. We can arrange that the starting configuration corresponding to an input $x$ is configuration (vertex) number $x$. This implies that $L$ is in NC.

If we are careful we can do better and show that $L$ is in fact in uniform NC (under various definitions of uniform). The idea now is that given two configurations $\sigma_1,\sigma_2$, it is easy to decide whether $\sigma_1$ can reach $\sigma_2$ in one step. According to the complexity zoo, this way we can show that PATH is NL-complete under first order reductions (uniform AC⁰ reductions). Since uniform NC is closed under first order reductions, this implies that NL is in uniform NC.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13387

 Ask a Question

 Download Related Notes/Documents