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

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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