0
$\begingroup$

What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?

$\endgroup$

1 Answer 1

0
$\begingroup$

If an $L$-complete problem (under first-order projection, or $NC^0$-reduction) has $NC^1$ circuit, then we have $L=NC^1$.

The $NC^1$ circuit for an arbitrary language $\mathbb{L}\in L$ is obtained by first projecting (in case of first-order projection) or doing a constant-depth transformation (in case of $NC^0$-reduction) to obtain an instance of the $L$-complete problem. Then, plugin the $NC^1$ circuit for the complete problem to solve the original problem overall.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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