Question regarding relation between NP and non-deterministic NC1

Question

Let $L$ be an arbitrary language in $NP$. Then,

1. For every input length $n$ we have a non-deterministic CNF formula for $L$, by the Cook-Levin theorem.
2. Every polynomial-sized formula can be converted to an $NC1$ circuit.

But that would mean $NP$ is in (logspace-uniform) non-deterministic $NC1$, which seems weird.

We know that class of languages with logspace uniform circuits is same as $P$. We also know uniform $NC1$ is in $P$; but we don't know if this inclusion is strict. Coming to the non-determinsitic world, logspace uniform non-determinsitic circuits is same as $NP$ (by the taleaux/Cook-Levin method). So I would hope that whether uniform non-determinsitic $NC1$ contains $NP$ or not should be "non-trivial" and an open question as well.

• D.W.: Why do you question your conclusion? Can you expand on why you believe you have gone wrong?

Answer 1

The conclusion doesn't sound weird to me. Nondeterministic circuits accept the same languages as nondeterministic NC1 circuits, by the Tseitin transform. In particular, the Tseitin transform will convert any polynomial-size deterministic circuit $C$ to a polynomial-size NC1 circuit $C'$, such that $C(x,y)$ holds iff $\exists z . C'(x,y,z)$ holds. Therefore, any language of the form

$$L=\{x \mid \exists y . C(x,y)\}$$

can also be expressed as

$$L=\{x \mid \exists y,z . C'(x,y,z)\}$$

where $C'$ is a NC1 circuit.