Five Shuffles Are Enough: Barrington's Theorem

Introduction

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.

Try It

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">This <strong>width-5 permutation branching program</strong> evaluates
<strong>(x₁ ∧ x₂) ∨ x₃</strong> using only permutations of {0,1,2,3,4}.
Toggle the input bits, then click <strong>Run program</strong> to watch the composition
build step by step. The program <em>accepts</em> when the final permutation is the identity.</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">Set bits and run the program.</div>
<div class="btns">
  <button id="run" type="button">Run program</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Barrington's theorem: NC¹ = width-5 permutation branching programs.
    // We implement a VERIFIED 12-step width-5 branching program for (x1 AND x2) OR x3.
    //
    // Construction via the NOR-commutator technique:
    //   OR(AND(x1,x2), x3) uses programs P_{NOT-AND} and P_{NOT-x3}:
    //     [P_{NOT-AND}, P_{NOT-x3}](x) = P_{NOT-AND}(x) * P_{NOT-x3}(x)
    //                                   * inv(P_{NOT-AND}(x)) * inv(P_{NOT-x3}(x))
    //   This equals the identity permutation iff NOT(NOT-AND and NOT-x3) = AND(x1,x2) OR x3.
    //
    // Permutations of {0,1,2,3,4} (width-5 means 5 states):
    //   e    = [0,1,2,3,4]  identity
    //   a    = [1,2,3,4,0]  5-cycle (0 1 2 3 4)
    //   ai   = [4,0,1,2,3]  a⁻¹
    //   b    = [1,2,0,3,4]  3-cycle (0 1 2)
    //   bi   = [2,0,1,3,4]  b⁻¹
    //   COMM = a*b*ai*bi = [0,4,1,3,2]  commutator [a,b]
    //   COMMi= COMM⁻¹  = [0,2,4,3,1]
    //   d    = [1,2,3,4,0] = a  (used for P_{NOT-x3})
    //   di   = [4,0,1,2,3] = ai
    //
    // The 12-step program (all perms in S₅, most from A₅):
    //   Steps 1-5:  P_{NOT-AND}(x1,x2)   → outputs COMMi iff NAND(x1,x2), e iff AND
    //   Step 6:     P_{NOT-x3}(x3)        → outputs a iff x3=0 (NOT x3=1), e iff x3=1
    //   Steps 7-11: inv(P_{NOT-AND})(x1,x2) → outputs COMM iff NAND, e iff AND
    //   Step 12:    inv(P_{NOT-x3})(x3)   → outputs ai iff x3=0, e iff x3=1
    //
    // This is verified correct for all 8 input combinations (see console).

function cp(p, q) { return p.map(i => q[i]); }
function isId(p) { return p.every((v, i) => v === i); }

const e    = [0,1,2,3,4];
const a    = [1,2,3,4,0];
const ai   = [4,0,1,2,3];
const b    = [1,2,0,3,4];
const bi   = [2,0,1,3,4];
const COMM = cp(cp(cp(a,b),ai),bi);  // = [0,4,1,3,2]
const COMMi= [0,2,4,3,1];            // inv(COMM)
const d    = a;   // generator for P_{NOT-x3}
const di   = ai;

// Each step: [varIdx (0=x1,1=x2,2=x3), perm_if_0, perm_if_1]
// 'null' perm means: use e (identity, regardless of variable).
// 'DUMMY' marker for unconditional steps (same perm for 0 and 1).
const PROG = [
  // --- P_{NOT-AND}: 5 steps ---
  // 4-step NAND commutator [a,b]: output=e iff NAND(x1,x2)
  [0, e,     a    ],  // step 1: x1 → {0:e, 1:a}
  [1, e,     b    ],  // step 2: x2 → {0:e, 1:b}
  [0, e,     ai   ],  // step 3: x1 → {0:e, 1:ai}
  [1, e,     bi   ],  // step 4: x2 → {0:e, 1:bi}
  [0, COMMi, COMMi],  // step 5: unconditional COMMi → output becomes COMMi iff NAND, e iff AND

  // --- P_{NOT-x3}: 1 step ---
  [2, d,     e    ],  // step 6: x3 → {0:d=a, 1:e}

  // --- inv(P_{NOT-AND}): 5 steps (reverse of P_{NOT-AND} with each perm inverted) ---
  [0, COMM,  COMM ],  // step 7: unconditional COMM (inverse of step 5's COMMi)
  [1, e,     b    ],  // step 8: x2 → {0:e, 1:b}  (inverse of bi = b, reversed from step 4)
  [0, e,     a    ],  // step 9: x1 → {0:e, 1:a}  (inverse of ai = a, reversed from step 3)
  [1, e,     bi   ],  // step 10: x2 → {0:e, 1:bi} (inverse of b = bi, reversed from step 2)
  [0, e,     ai   ],  // step 11: x1 → {0:e, 1:ai} (inverse of a = ai, reversed from step 1)

  // --- inv(P_{NOT-x3}): 1 step ---
  [2, di,    e    ],  // step 12: x3 → {0:di=ai, 1:e}
];

const VAR_NAMES = ['x₁', 'x₂', 'x₃'];
const SECTION_LABELS = [
  'P_NOT-AND step 1', 'P_NOT-AND step 2', 'P_NOT-AND step 3', 'P_NOT-AND step 4',
  'P_NOT-AND step 5 (∗)',
  'P_NOT-x₃',
  'P_NOT-AND⁻¹ step 1 (∗)', 'P_NOT-AND⁻¹ step 2', 'P_NOT-AND⁻¹ step 3',
  'P_NOT-AND⁻¹ step 4', 'P_NOT-AND⁻¹ step 5',
  'P_NOT-x₃⁻¹',
];

// Verify all 8 truth-table cases at load time
function evalProg(x1v, x2v, x3v) {
  const inputs = [x1v, x2v, x3v];
  let perm = e.slice();
  const trace = [];
  for (let i = 0; i < PROG.length; i++) {
    const [vi, p0, p1] = PROG[i];
    const chosen = inputs[vi] ? p1 : p0;
    perm = cp(perm, chosen);
    trace.push({ step: i + 1, label: SECTION_LABELS[i], varName: VAR_NAMES[vi],
                 bitVal: inputs[vi], chosen, after: perm.slice() });
  }
  return { perm, trace };
}

let allOk = true;
for (let v = 0; v < 8; v++) {
  const x1v=(v>>2)&1, x2v=(v>>1)&1, x3v=v&1;
  const expected = ((x1v && x2v) || x3v) ? 1 : 0;
  const { perm } = evalProg(x1v, x2v, x3v);
  const got = isId(perm) ? 1 : 0;
  if (expected !== got) {
    allOk = false;
    console.error(fmt('Verification FAILED: x1=%x1v% x2=%x2v% x3=%x3v% expected=%expected% got=%got%', { x1v: x1v, x2v: x2v, x3v: x3v, expected: expected, got: got }));
  }
}
if (allOk) console.log('Barrington program verified correct for all 8 inputs.');

// ── UI ────────────────────────────────────────────────────────────────────────────
function permEls(p) {
  return '<div class="perm">' + p.map(v => '<span>'+v+'</span>').join('') + '</div>';
}

function renderEmpty() {
  const area = document.getElementById('steps-area');
  area.innerHTML = fmt('<div class="step"><span class="step-label">Start</span><span></span><span class="arrow">→</span>%permEls%</div>', { permEls: permEls(e) });
}

function renderTrace(trace) {
  const area = document.getElementById('steps-area');
  const rows = [fmt('<div class="step"><span class="step-label">Start</span><span></span><span class="arrow">→</span>%permEls%</div>', { permEls: permEls(e) })];
  trace.forEach(s => {
    const accepted = isId(s.after);
    const cls = 'step ' + (accepted ? 'accepted' : 'rejected');
    const bit = s.bitVal ? '= 1' : '= 0';
    rows.push(
      '<div class="'+cls+'"><span class="step-label">'+s.label+'</span>'
      + '<span class="step-bit">'+s.varName+bit+'</span>'
      + '<span class="arrow">→</span>'
      + permEls(s.after)
      + '</div>'
    );
  });
  area.innerHTML = rows.join('');
  area.scrollTop = area.scrollHeight;
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + cls;
}

document.getElementById('run').addEventListener('click', () => {
  const x1v = document.getElementById('x1').checked ? 1 : 0;
  const x2v = document.getElementById('x2').checked ? 1 : 0;
  const x3v = document.getElementById('x3').checked ? 1 : 0;
  const { perm, trace } = evalProg(x1v, x2v, x3v);
  renderTrace(trace);
  const accepted = isId(perm);
  const fval = ((x1v && x2v) || x3v) ? 'true' : 'false';
  if (accepted) {
    setStatus(fmt('✓ Final permutation is the identity → ACCEPT. Formula = %fval%.', { fval: fval }), 'ok');
  } else {
    setStatus(fmt('✗ Final permutation [%perm%] ≠ identity → REJECT. Formula = %fval%.', { perm: perm.join(' '), fval: fval }), 'bad');
  }
});

document.getElementById('reset').addEventListener('click', () => {
  ['x1','x2','x3'].forEach(id => { document.getElementById(id).checked = false; });
  renderEmpty();
  setStatus('Set bits and run the program.', 'idle');
});

renderEmpty();
if (!allOk) setStatus('⚠ Internal error — see console.', 'bad');

<p class="hint">This <strong>width-5 permutation branching program</strong> evaluates
<strong>(x₁ ∧ x₂) ∨ x₃</strong> using only permutations of {0,1,2,3,4}.
Toggle the input bits, then click <strong>Run program</strong> to watch the composition
build step by step. The program <em>accepts</em> when the final permutation is the identity.</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">Set bits and run the program.</div>
<div class="btns">
  <button id="run" type="button">Run program</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Barrington's theorem: NC¹ = width-5 permutation branching programs.
    // We implement a VERIFIED 12-step width-5 branching program for (x1 AND x2) OR x3.
    //
    // Construction via the NOR-commutator technique:
    //   OR(AND(x1,x2), x3) uses programs P_{NOT-AND} and P_{NOT-x3}:
    //     [P_{NOT-AND}, P_{NOT-x3}](x) = P_{NOT-AND}(x) * P_{NOT-x3}(x)
    //                                   * inv(P_{NOT-AND}(x)) * inv(P_{NOT-x3}(x))
    //   This equals the identity permutation iff NOT(NOT-AND and NOT-x3) = AND(x1,x2) OR x3.
    //
    // Permutations of {0,1,2,3,4} (width-5 means 5 states):
    //   e    = [0,1,2,3,4]  identity
    //   a    = [1,2,3,4,0]  5-cycle (0 1 2 3 4)
    //   ai   = [4,0,1,2,3]  a⁻¹
    //   b    = [1,2,0,3,4]  3-cycle (0 1 2)
    //   bi   = [2,0,1,3,4]  b⁻¹
    //   COMM = a*b*ai*bi = [0,4,1,3,2]  commutator [a,b]
    //   COMMi= COMM⁻¹  = [0,2,4,3,1]
    //   d    = [1,2,3,4,0] = a  (used for P_{NOT-x3})
    //   di   = [4,0,1,2,3] = ai
    //
    // The 12-step program (all perms in S₅, most from A₅):
    //   Steps 1-5:  P_{NOT-AND}(x1,x2)   → outputs COMMi iff NAND(x1,x2), e iff AND
    //   Step 6:     P_{NOT-x3}(x3)        → outputs a iff x3=0 (NOT x3=1), e iff x3=1
    //   Steps 7-11: inv(P_{NOT-AND})(x1,x2) → outputs COMM iff NAND, e iff AND
    //   Step 12:    inv(P_{NOT-x3})(x3)   → outputs ai iff x3=0, e iff x3=1
    //
    // This is verified correct for all 8 input combinations (see console).

function cp(p, q) { return p.map(i => q[i]); }
function isId(p) { return p.every((v, i) => v === i); }

const e    = [0,1,2,3,4];
const a    = [1,2,3,4,0];
const ai   = [4,0,1,2,3];
const b    = [1,2,0,3,4];
const bi   = [2,0,1,3,4];
const COMM = cp(cp(cp(a,b),ai),bi);  // = [0,4,1,3,2]
const COMMi= [0,2,4,3,1];            // inv(COMM)
const d    = a;   // generator for P_{NOT-x3}
const di   = ai;

// Each step: [varIdx (0=x1,1=x2,2=x3), perm_if_0, perm_if_1]
// 'null' perm means: use e (identity, regardless of variable).
// 'DUMMY' marker for unconditional steps (same perm for 0 and 1).
const PROG = [
  // --- P_{NOT-AND}: 5 steps ---
  // 4-step NAND commutator [a,b]: output=e iff NAND(x1,x2)
  [0, e,     a    ],  // step 1: x1 → {0:e, 1:a}
  [1, e,     b    ],  // step 2: x2 → {0:e, 1:b}
  [0, e,     ai   ],  // step 3: x1 → {0:e, 1:ai}
  [1, e,     bi   ],  // step 4: x2 → {0:e, 1:bi}
  [0, COMMi, COMMi],  // step 5: unconditional COMMi → output becomes COMMi iff NAND, e iff AND

  // --- P_{NOT-x3}: 1 step ---
  [2, d,     e    ],  // step 6: x3 → {0:d=a, 1:e}

  // --- inv(P_{NOT-AND}): 5 steps (reverse of P_{NOT-AND} with each perm inverted) ---
  [0, COMM,  COMM ],  // step 7: unconditional COMM (inverse of step 5's COMMi)
  [1, e,     b    ],  // step 8: x2 → {0:e, 1:b}  (inverse of bi = b, reversed from step 4)
  [0, e,     a    ],  // step 9: x1 → {0:e, 1:a}  (inverse of ai = a, reversed from step 3)
  [1, e,     bi   ],  // step 10: x2 → {0:e, 1:bi} (inverse of b = bi, reversed from step 2)
  [0, e,     ai   ],  // step 11: x1 → {0:e, 1:ai} (inverse of a = ai, reversed from step 1)

  // --- inv(P_{NOT-x3}): 1 step ---
  [2, di,    e    ],  // step 12: x3 → {0:di=ai, 1:e}
];

const VAR_NAMES = ['x₁', 'x₂', 'x₃'];
const SECTION_LABELS = [
  'P_NOT-AND step 1', 'P_NOT-AND step 2', 'P_NOT-AND step 3', 'P_NOT-AND step 4',
  'P_NOT-AND step 5 (∗)',
  'P_NOT-x₃',
  'P_NOT-AND⁻¹ step 1 (∗)', 'P_NOT-AND⁻¹ step 2', 'P_NOT-AND⁻¹ step 3',
  'P_NOT-AND⁻¹ step 4', 'P_NOT-AND⁻¹ step 5',
  'P_NOT-x₃⁻¹',
];

// Verify all 8 truth-table cases at load time
function evalProg(x1v, x2v, x3v) {
  const inputs = [x1v, x2v, x3v];
  let perm = e.slice();
  const trace = [];
  for (let i = 0; i < PROG.length; i++) {
    const [vi, p0, p1] = PROG[i];
    const chosen = inputs[vi] ? p1 : p0;
    perm = cp(perm, chosen);
    trace.push({ step: i + 1, label: SECTION_LABELS[i], varName: VAR_NAMES[vi],
                 bitVal: inputs[vi], chosen, after: perm.slice() });
  }
  return { perm, trace };
}

let allOk = true;
for (let v = 0; v < 8; v++) {
  const x1v=(v>>2)&1, x2v=(v>>1)&1, x3v=v&1;
  const expected = ((x1v && x2v) || x3v) ? 1 : 0;
  const { perm } = evalProg(x1v, x2v, x3v);
  const got = isId(perm) ? 1 : 0;
  if (expected !== got) {
    allOk = false;
    console.error(fmt('Verification FAILED: x1=%x1v% x2=%x2v% x3=%x3v% expected=%expected% got=%got%', { x1v: x1v, x2v: x2v, x3v: x3v, expected: expected, got: got }));
  }
}
if (allOk) console.log('Barrington program verified correct for all 8 inputs.');

// ── UI ────────────────────────────────────────────────────────────────────────────
function permEls(p) {
  return '<div class="perm">' + p.map(v => '<span>'+v+'</span>').join('') + '</div>';
}

function renderEmpty() {
  const area = document.getElementById('steps-area');
  area.innerHTML = fmt('<div class="step"><span class="step-label">Start</span><span></span><span class="arrow">→</span>%permEls%</div>', { permEls: permEls(e) });
}

function renderTrace(trace) {
  const area = document.getElementById('steps-area');
  const rows = [fmt('<div class="step"><span class="step-label">Start</span><span></span><span class="arrow">→</span>%permEls%</div>', { permEls: permEls(e) })];
  trace.forEach(s => {
    const accepted = isId(s.after);
    const cls = 'step ' + (accepted ? 'accepted' : 'rejected');
    const bit = s.bitVal ? '= 1' : '= 0';
    rows.push(
      '<div class="'+cls+'"><span class="step-label">'+s.label+'</span>'
      + '<span class="step-bit">'+s.varName+bit+'</span>'
      + '<span class="arrow">→</span>'
      + permEls(s.after)
      + '</div>'
    );
  });
  area.innerHTML = rows.join('');
  area.scrollTop = area.scrollHeight;
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + cls;
}

document.getElementById('run').addEventListener('click', () => {
  const x1v = document.getElementById('x1').checked ? 1 : 0;
  const x2v = document.getElementById('x2').checked ? 1 : 0;
  const x3v = document.getElementById('x3').checked ? 1 : 0;
  const { perm, trace } = evalProg(x1v, x2v, x3v);
  renderTrace(trace);
  const accepted = isId(perm);
  const fval = ((x1v && x2v) || x3v) ? 'true' : 'false';
  if (accepted) {
    setStatus(fmt('✓ Final permutation is the identity → ACCEPT. Formula = %fval%.', { fval: fval }), 'ok');
  } else {
    setStatus(fmt('✗ Final permutation [%perm%] ≠ identity → REJECT. Formula = %fval%.', { perm: perm.join(' '), fval: fval }), 'bad');
  }
});

document.getElementById('reset').addEventListener('click', () => {
  ['x1','x2','x3'].forEach(id => { document.getElementById(id).checked = false; });
  renderEmpty();
  setStatus('Set bits and run the program.', 'idle');
});

renderEmpty();
if (!allOk) setStatus('⚠ Internal error — see console.', 'bad');

Result

Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/barrington-theorem/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Barrington's Theorem

The surprising power of permuting just five elements