1
$\begingroup$

Most proofs of the problem that I have seen stop at proving $\textbf{NL}\subseteq \textbf{NC}^2$ and not explicitly point out the circuit. I'm trying to show that $\textbf{NC}$ circuit family can compute log space reduction by constructing corresponding $\textbf{NC}^2$, using the definition of implicitly logspace computable function according to Arora and Barak:

A function $f : \{0, 1\}^∗\rightarrow \{0, 1\}^∗$ is implicitly logspace computable, if $f$ is polynomially bounded (i.e., there’s some $c$ such that $|f(x)|\le |x|^c$ for every $x\in \{0, 1\}^∗$ ) and the languages $L_f = \{\langle x, i\rangle | f (x)_i = 1\}$ and $L'_f = \{\langle x, i\rangle | i \le |f(x)|\}$ are in $\textbf{L}$.

Where $f(x)_i$ is the $i$th bit of $f(x)$. In my opinion, we can compute $i$th bit of $f(x)$ and determine the length of $f(x)$ by logspace machines.

Because $L_f\in\textbf{L}$, there is a $\textbf{NC}^2$ circuit family decides $L_f$. $f(x)_i$ is computed by a circuit $C_{|\langle x,i\rangle|}(\langle x, i\rangle)$. We could generate all $f(x)$ bits by merging $|f(x)|=|x|^c$ circuits $C_{|\langle x,i\rangle|}$ for $i=0,\ldots,|x|^c$ "hard-wired" their input gates for $i$ in binary encode, such as $C(\langle x,0\rangle),C(\langle x,1\rangle),C(\langle x,10\rangle),$ etc. The final circuit has $O(\log^2n)$ depth and $poly(n)$ size because each circuit component also has $O(\log^2n)$ depth and $poly(n)$ size.

Does my proof have any defect?

asked Oct 18, 2024 at 17:32
$\endgroup$

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.