In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the first layer consists of OR (or AND) gates, then the second layer consists of AND (or OR) gates, the third layer consists of OR(AND) gates, and so on, what is the proof of this conclusion? Or any reference? I remember the proof that the PARITY problem needs exponential circuit complexity used this fact when using Håstad switching Lemma. Thanks!

Note: we don't need CNF(or DNF) here, because that corresponds to 2 layers and exponential number of gates. In general, the circuit above can be arranged as multiple layers, so CNF(DNF) is not necessary.

  • 2
    $\begingroup$ We don't need DNF or CNF but the fact that every negation-free formula has an equivalent negation-free DNF and CNF already gives you two proofs of the result you want. Why do you need a third proof? $\endgroup$ – David Richerby Jun 17 '16 at 8:30

Let $r$ be the root of your circuit (without loss of generality, an OR gate), and let $V_i$ consist of those gates at distance $i$ from $r$. Assign (in your mind) a layer for each gate: layer 0 for the root, layer $2i-1$ for an AND gate in $V_i$, and layer $2i$ for an OR gate in $V_i$. The result is almost what you want – the only difference is that edges could span more than one layer.

In order to fix the problem, for each gate $g$, create gates in all layers above it (i.e., with smaller number) of the correct type, and connect them in a path (so all the new gates will have in-degree 1). Now you can arrange that each edge span exactly one layer.

Starting with a circuit of depth $D$ and $n$ gates, we have created a circuit of depth $2D$ and at most $nD$ gates. In particular, if the original circuit had polynomial size then so does the new one (with a different polynomial), and if the original circuit had constant depth (or logarithmic, or polylogarithmic) then so does the new one.


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.