NC (complexity) - Barrington's Theorem

Barrington's Theorem

A branching program with n variables of width k and length m consists of a sequence of m instructions. Each of the instructions is a tuple (i, p, q) where i is the index of variable to check (1 ≤ i ≤ n), and p and q are functions from {1, 2, ..., k} to {1, 2, ..., k}. Numbers 1, 2, ..., k are called states of the branching program. The program initially starts in state 1, and each instruction (i, p, q) changes the state from x to p(x) or q(x), depending on whether the ith variable is 0 or 1.

A family of branching programs consists of a branching program with n variables for each n.

It is easy to show that every language L on {0,1} can be recognized by a family of branching programs of width 4 and exponential length, or by a family of exponential width and linear length.

Every regular language on {0,1} can be recognized by a family of branching programs of constant width and linear number of instructions (since a DFA can be converted to a branching program). BWBP denotes the class of languages recognizable by a family of branching programs of bounded width and polynomial length.

Barrington's theorem says that is exactly nonuniform NC1. The proof uses the nonsolvability of the symmetric group S₅.

The theorem is rather surprising. It implies that the majority function can be computed by a family of branching programs of constant width and polynomial size, while intuition might suggest that to achieve polynomial size, one needs a linear number of states.