CNF and small-depth circuits

Question

I'm reading on small-depth circuits. Since every formula can be turned into a CNF formula, which has depth at most 3, why should we study deeper circuits? Is it because convertion to CNF may result in an explosive blow-up? If so, can you give an example?

Answer 1

Much of the interest in circuits stems from the following implication: $$ \mathsf{NP} \not\subseteq \mathsf{P/poly} \Longrightarrow \mathsf{P} \neq \mathsf{NP}. $$ In words, if we show that some problem in NP doesn't have polynomial size circuits then we have proved that P≠NP.

Unfortunately, we don't really know how to prove lower bounds on general circuits. We do know how to prove lower bounds for constant depth circuits and for monotone circuits, which is the main reason we are interested in these models at all.

We already know of functions in $\mathsf{NP}$ which don't have polynomial size constant depth circuits. Unfortunately, these functions are in $\mathsf{P}$, and so won't help in proving $\mathsf{NP} \not\subseteq \mathsf{P/poly}$. What we want is to improve our techniques so that they apply for circuits with polynomial depth — that would show that $\mathsf{NP} \not\subseteq \mathsf{P/poly}$.

Now, to your question. While it is true that every function can be represented as a CNF and so as a constant depth circuit, sometimes allowing larger depths makes a big difference. For example, Parity has an exponential size CNF (and even exponential size constant depth circuits), but has a polynomial size circuit of logarithmic depth (and even a polynomial size formula). In other words, Parity exhibits an exponential blowup when converting from circuit to CNF. This shows that lower bounds on CNFs (probably) won't be able to separate P and NP according to the program laid out above.