Barrington's Theorem

Imagine you are allowed to shuffle a deck of exactly five cards. At each step you peek at one bit of the input, then choose which shuffle to apply. After reading all the bits you check whether the deck ended up in the original order. How expressive can such a simple process be?

The answer — given by David A. Mix Barrington in 1989 — is stunning: this tiny model can compute every function that can be computed by efficient parallel circuits. It is proven (Barrington, 1989) that the class NC¹ (problems solvable by Boolean circuits of logarithmic depth and polynomial size) equals exactly the class of languages recognized by width-5 polynomial-length permutation branching programs.

Width 4 is too weak — four elements are not enough. Width 5 hits a sweet spot because the symmetric group $S_5$ is non-solvable: it contains the alternating group $A_5$, which is simple and non-abelian. That algebraic accident is the engine behind the entire theorem, and it connects everyday computation to deep abstract algebra.

The demo below runs a width-5 permutation branching program that evaluates the Boolean formula $(x_1 \land x_2) \lor x_3$. Each row of the program reads one input bit and applies one of two permutations of $\{0,1,2,3,4\}$: the identity if the bit is 0, or a non-trivial permutation if the bit is 1.

Toggle the three input bits, then click Run program to watch the permutations compose step by step. The program accepts when the final composition is the identity permutation, and rejects otherwise.

<p class="hint">{{hint_p}}</p>
<div class="inputs">
  <label><input type="checkbox" id="x1"> x₁</label>
  <label><input type="checkbox" id="x2"> x₂</label>
  <label><input type="checkbox" id="x3"> x₃</label>
</div>
<div id="steps-area"></div>
<div class="status" id="status">{{status_idle}}</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.inputs { display: flex; gap: 1.4rem; margin-bottom: .9rem; }
.inputs label { display: flex; align-items: center; gap: .4rem; font-weight: 700;
                font-size: 1rem; cursor: pointer; user-select: none; }
input[type=checkbox] { width: 18px; height: 18px; cursor: pointer; accent-color: #1d3557; }
#steps-area { display: flex; flex-direction: column; gap: 5px; margin-bottom: .7rem;
              max-height: 260px; overflow-y: auto; }
.step { display: grid; grid-template-columns: 100px 60px 20px 1fr;
        align-items: center; gap: .4rem; padding: 5px 8px;
        border-radius: 7px; background: #edf2f7; border: 1px solid #cdd9e3;
        font-size: .83rem; font-family: ui-monospace, monospace; }
.step.accepted { background: #d4edda; border-color: #6abf8a; }
.step.rejected { background: #fde8e8; border-color: #e08b8b; }
.step-label { font-weight: 700; color: #1d3557; }
.step-bit { color: #555; font-size: .8rem; }
.arrow { color: #aaa; text-align: center; }
.perm { display: flex; gap: 3px; }
.perm span { display: inline-flex; align-items: center; justify-content: center;
             width: 20px; height: 20px; border-radius: 4px;
             background: #dce8f5; font-size: .78rem; font-weight: 600; color: #1d3557; }
.step.accepted .perm span { background: #b8e0c8; color: #0a5c22; }
.step.rejected .perm span { background: #f5c6c6; color: #9b1c1c; }
.status { font-size: .95rem; font-weight: 600; margin: .3rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.idle { color: #555; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice that the program never stores any Boolean state — it only tracks which permutation has accumulated so far. Yet by choosing the permutations carefully, the composition encodes the whole formula. This is Barrington's key insight: the non-solvability of $S_5$ provides exactly the algebraic headroom needed to simulate AND with commutator gadgets.

How hard is computing with tiny permutation programs, really?

• Width 1 programs are trivial: the only permutation of one element is the identity, so you can recognize only the empty language and $\Sigma^*$.
• Width 2–4 programs are too weak: they can only recognize solvable languages (those in the quasi-AC⁰ closure of parity). Barrington proved this via the solvable group theory — small-width programs correspond to solvable groups, which cannot express all of NC¹.
• Width 5 is exactly NC¹. The key is the commutator construction. The commutator of two permutations $\sigma$ and $\tau$ is $[\sigma,\tau] = \sigma\tau\sigma^{-1}\tau^{-1}$. If the permutations are chosen from $A_5$, the commutator can implement a controlled operation: it equals the identity when a subprogram accepts, and a fixed non-identity permutation when it rejects. This lets you simulate AND and NOT gates, and hence every Boolean circuit.
• The depth-to-length blow-up is polynomial: a depth-$d$ circuit of size $s$ translates to a branching program of length at most $4^d \cdot s$, which is polynomial when $d = O(\log n)$.
• Width 5 cannot be lowered: no group of order $\leq 4$ is non-solvable, so width 4 is provably insufficient for all of NC¹.

The theorem also implies that NC¹ ⊆ L (logarithmic space), since a width-5 program can be simulated by a log-space Turing machine that simply tracks the current permutation (one of at most $5! = 120$ possibilities). This is one of the tightest known inclusions between circuit and space complexity classes. Compare it with the still-open question of whether P equals NP — Barrington's result is a rare proved equality across seemingly different models.

Barrington's theorem is not just a beautiful curiosity — it has concrete consequences:

• Complexity lower bounds: to show a function is not in NC¹, it suffices to show it cannot be computed by any polynomial-length width-5 branching program. This has driven many lower-bound proofs in algebraic circuit complexity.
• Algebraic automata theory: the theorem precisely maps the Krohn-Rhodes decomposition of finite automata onto circuit complexity classes. The solvability hierarchy of groups corresponds to levels of the AC⁰ and NC¹ hierarchy.
• Cryptographic protocols: oblivious branching programs (where both branches apply a permutation, hiding which bit was read) are used in private information retrieval and secure computation. Barrington's encoding is directly relevant to these constructions.
• Parallel computation: understanding NC¹ helps classify which problems can be solved extremely fast in parallel. Problems in NC¹ include integer addition, string matching, and regular language recognition.
• Teaching group theory via computation: the theorem gives a concrete reason why $A_5$ being simple matters — it is the algebraic reason why you cannot get away with width 4. See also P vs NP and circuit complexity for how NC classes fit into the big picture.

Barrington's theorem delivers one of the most satisfying punches in complexity theory: a model that looks laughably weak — shuffle five cards, never remember anything else — turns out to be exactly as powerful as the best parallel circuits in NC¹. Not approximately, not almost: exactly.

The reason hides in abstract algebra. The symmetric group $S_5$ is non-solvable precisely because $A_5$ is a non-abelian simple group, and that algebraic property translates into computational expressiveness through the commutator gadget. Width 4 falls short for the same algebraic reason. This tight correspondence between group theory and computation remains one of the most elegant proved results in all of theoretical computer science.

So the next time you shuffle a five-element sequence, remember: you are operating in a world rich enough to compute anything a logarithmic-depth circuit can — no memory required, just the right choice of permutations at every step.