Question

Prove that if$\mathbf{A}{\mathbf{⩽}}_{\mathbf{L}}\mathbf{B}$ and B is in NC then A is in NC

Short answer

Using the fact of circuit evaluation i.e., “the problem of circuit evaluation is P complete”, it can solve the above problem.

Step-by-step solution

Definition of circuit Evaluation

The circuit evaluation problem is the computational problem of calculating the output of a given Boolean circuit given an input.

For a circuit C and input string w, the value of C on w can be written as$C\left(w\right)$.

Suppose,.

Understanding the required theorem to be applied

Consider the theorem,

Suppose$t\text{:}M\to M$ be a function, where $t\left(m\right)⩾m$.

If $w\in \text{TIME}\left(t\left(m\right)\right)$, then the complexity of circuit A is given by $O\left(t^2\left(m\right)\right)$.

According to the above theorem,

On input w, the production of a circuit takes place by the reduction. The process of reduction simulates the Turning Machine for w in polynomial time. The w itself can be taken as an input to the circuit.

The above theorem shows the way of reduction of a language w

(Which is in P) to$\text{CIRCUIT}-\text{VALUE}$.

A $\log space$is used to carry out the reduction because the circuit produced by it contains a repetitive and a simple structure.

Hence, it shows that CIRCUIT-VALUE is P complete and circuit produced by it has a repetitive structure. Therefore, if $A{⩽}_{L}B$ and B is in NC then A is in NC.