# 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$

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.

• Your language does seem to be in logspace. Oct 26, 2021 at 6:08
• @YuvalFilmus Thank you, Yuval. Already noticed that. I'll post an answer soon. Oct 27, 2021 at 7:12

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.
$$L$$ is complete because every language in logspace is complete.