What class is the language $(C,(v_i)_{i=1}^m,x)$ complete to s.t. $C(x)$ is a boolean circuit with $m$ gates with values $\{v_i\}_{i=1}^m$

Question

Given the following language: $$ L=\left\{\,(\,C,\,\{v_i\}_{i=1}^m, \,x\,) \enspace :\enspace \substack{C(x) \text{ is a boolean circuit with } m \text{ gates} \\i\text{'th gate value is } v_i \text{ on input } x} \right\} $$ I need to find out to what known class $L$ is complete to with respect to logspace reductions.

I think that it is impossible to reduce $\text{CVAL}$ to $L$ because if we can compute gate's values $\{v_i\}_{i=1}^m$'s we could solve $\mathrm{CVAL}$ in logspace which would imply $\mathbf{P = LOG}$.

I also think that $L\in\mathbf{P}$ because we can calculate $C(x)$ and of course all the gates $\{v_i\}_{i=1}^m$ using BFS as in computing every boolean circuit value.

Please advise. Thank you.

Answer 1

The language $L$ is $\mathbf{LOG}$-complete.

All we need to check is for each gate, its value (from the $(v_i)_{i=1}^{m}$ input) is consistent with its connected gates (i.e. children).

In other words, just iterate all the gates and make sure the $(v_i)_{i=1}^{m}$'s are consistent.

This can be done in logspace because we just need to hold the pointer to the gate we are currently checking.

$L$ is complete because every language in logspace is complete.