4
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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 AC0 reductions). Since uniform NC is closed under first order reductions, this implies that NL is in uniform NC.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.