# CNF and small-depth circuits

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?

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.
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}$.
• You don't need XOR. You do it recursively, using $A \oplus B = (A \land \lnot B) \lor (\lnot A \land B)$. The size of the formula satisfies the recurrence $T(n) = 4T(n/2) + O(1)$ whose solution is $T(n) = \Theta(n^2)$. – Yuval Filmus Sep 6 '17 at 11:13