Boolean circuit with true value

Question

Let $$L=\left\{,円\langle,円B_n,,円 ,円x,円\rangle:\enspace\substack{B_n \text{ is a boolean circuit and } \\x \in \{0, 1\}^n\text{such that }B_n(x) = 1}\right\}$$

I want to prove that $L$ is $\textbf{P}$-complete.

We know that a language is $\textbf{P}$-complete if it is in $\textbf{P}$ and every language in $\textbf{P}$ is logspace- reducible to it.

We need to prove that

1. $L$ is in $\textbf{P}$, and
2. $L$ is $\textbf{P}$-hard (i.e., every language $L' \in \textbf{P}$ reduces to $L$ via a logspace reduction).

The fact that $L$ is in $\textbf{P}$ maybe easy. We can topologically order the gates of the input circuit (which is a directed acyclic graph), and then traverse its gates in that order, starting from the inputs. In the process of this traversal, we compute and assign the values to each gate we encounter (based on the values to the inputs to the gate that were already computed earlier). This yields a polynomial-time algorithm for $L$.

But I am not able to prove the $\textbf{P}$-hardness in logspace? Anybody help me to prove the reduction?

• Nathaniel: There is a proof of a reduction in there, but it does not seem trivial at all.