1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Your language does seem to be in logspace. $\endgroup$ Oct 26 '21 at 6:08
  • $\begingroup$ @YuvalFilmus Thank you, Yuval. Already noticed that. I'll post an answer soon. $\endgroup$
    – Dennis
    Oct 27 '21 at 7:12
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.