2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What uniformity condition do you impose? ​ ​ $\endgroup$ – user12859 Nov 5 '15 at 15:04
  • $\begingroup$ Log-space uniformity! $\endgroup$ – Vikash B Nov 5 '15 at 15:13
  • $\begingroup$ Do you have to use the approach described in your question? ​ ​ $\endgroup$ – user12859 Nov 5 '15 at 15:22
  • $\begingroup$ Yes, i have seen another approach and i want to know if i can do it using mine. $\endgroup$ – Vikash B Nov 5 '15 at 15:23
  • $\begingroup$ 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$.) $\;\;\;\;$ $\endgroup$ – user12859 Nov 5 '15 at 15:30
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why do we require the subscript i in f(x) can't the transducer directly compute the entire output f(x)? $\endgroup$ – Vikash B Nov 5 '15 at 19:45
  • $\begingroup$ 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. $\endgroup$ – Ariel Nov 5 '15 at 19:50

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.