Previous slide Next slide Back to the first slide View text version


Notes:

Recall that $\NC^1$ consists of the languages accepted by constant fan-in and logarithmic depth circuits.

One can easily show that every language that accepts bounded-width poly-size branching programs must lie in $\NC^1$ by divide and conquer. However, it did not seem possible to count in a bounded-width program so many believed that majority, an $\NC^1$ function, did not have bounded-width branching programs. In fact, Yao \cite{Yao-Arg} showed a super-polynomial lower bound for width-two branching programs to compute majority.

Barrington used the fact that $S_5$, the set of permutations on five elements, formed a nonsolvable group. More precisely there are two five cycles $\sigma_1=(1 2 3 4 5)$ and $\sigma_2=(1 3 5 4 2)$ in $S_5$, such that $\sigma_1\sigma_2\sigma_1^{-1}\sigma_2^{-1}=(1 3 2 5 4)$ is a five cycle. Barrington uses this simple fact to capture the computation of a circuit by just remembering one of these cycles.