Editing NC (complexity) (section)

===Proof of Barrington's theorem===
A branching program of constant width and polynomial size can be easily converted (via divide-and-conquer) to a circuit in '''NC'''<sup>1</sup>.

Conversely, suppose a circuit in '''NC'''<sup>1</sup> is given. Without loss of generality, assume it uses only AND and NOT gates.

{{math_theorem|name=Lemma 1|If there exists a branching program that sometimes works as a permutation ''P'' and sometimes as a permutation ''Q'', by right-multiplying permutations in the first instruction by {{var|α}}, and in the last instruction left-multiplying by {{var|β}}, we can make a circuit of the same length that behaves as {{var|β}}''P''{{var|α}} or {{var|β}}''Q''{{var|α}}, respectively.}}

Call a branching program α-computing a circuit ''C'' if it works as identity when {{var|C}}'s output is 0, and as {{var|α}} when {{var|C}}'s output is 1.

As a consequence of Lemma 1 and the fact that all cycles of length 5 are [[Conjugacy class|conjugate]], for any two 5-cycles {{var|α}}, {{var|β}}, if there exists a branching program α-computing a circuit ''C'', then there exists a branching program β-computing the circuit ''C'', of the same length.

{{math_theorem|name=Lemma 2|1=There exist 5-cycles {{var|γ}}, {{var|δ}} such that their [[commutator]] {{math|1=''ε''=''γδγ''<sup>−1</sup>''δ''<sup>−1</sup>}} is a 5-cycle. For example, {{var|γ}} = (1 2 3 4 5), {{var|δ}} = (1 3 5 4 2) giving {{var|ε}} = (1 3 2 5 4).}}
{{math proof|1=We will now prove Barrington's theorem by induction:

Suppose we have a circuit ''C'' which takes inputs ''x''<sub>1</sub>,...,''x''<sub>''n''</sub> and assume that for all subcircuits ''D'' of ''C'' and 5-cycles α, there exists a branching program α-computing ''D''. We will show that for all 5-cycles α, there exists a branching program α-computing ''C''.

* If the circuit ''C'' simply outputs some input bit ''x<sub>i</sub>'', the branching program we need has just one instruction: checking {{var|x<sub>i</sub>}}'s value (0 or 1), and outputting the identity or {{var|α}} (respectively).
* If the circuit ''C'' outputs ¬''A'' for some different circuit ''A'', create a branching program {{var|α}}<sup>−1</sup>-computing ''A'' and then multiply the output of the program by α. By Lemma 1, we get a branching program for ''A'' outputting the identity or α, i.e. {{var|α}}-computing ¬''A''=''C''.
* If the circuit ''C'' outputs {{nowrap|''A''∧''B''}} for circuits ''A'' and ''B'', join the branching programs that {{var|γ}}-compute ''A'', {{var|δ}}-compute ''B'', {{var|γ}}<sup>−1</sup>-compute ''A'', and δ<sup>−1</sup>-compute B for a choice of 5-cycles γ and δ such that their commutator {{math|1=''ε''=''γδγ''<sup>−1</sup>''δ''<sup>−1</sup>}} is also a 5-cycle. (The existence of such elements was established in Lemma 2.) If one or both of the circuits outputs 0, the resulting program will be the identity due to cancellation; if both circuits output 1, the resulting program will output the commutator {{var|ε}}. In other words, we get a program {{var|ε}}-computing {{nowrap|''A''∧''B''}}. Because {{var|ε}} and {{var|α}} are two 5-cycles, they are conjugate, and hence there exists a program {{var|α}}-computing {{nowrap|''A''∧''B''}} by Lemma 1.

By assuming the subcircuits have branching programs so that they are {{var|α}}-computing for all 5-cycles {{math|{{var|α}}∈''S''<sub>5</sub>}}, we have shown ''C'' also has this property, as required.
}}
The size of the branching program is at most 4<sup>{{var|d}}</sup>, where ''d'' is the depth of the circuit. If the circuit has logarithmic depth, the branching program has polynomial length.