Introduction

Imagine a computer built entirely from AND gates and OR gates, wired in layers so shallow that any signal travels through at most a constant number of them. This is the AC⁰ model — a circuit where each gate can fan in as many wires as you like, but the total depth is bounded.

AC⁰ circuits are surprisingly powerful. They can add numbers, compare strings, compute majority over small inputs. So you might expect them to handle any reasonable arithmetic task — including checking whether the number of 1-bits in an input is even or odd (computing parity, or MOD 2).

In 1987, Alexander Razborov and Roman Smolensky independently proved the opposite: no AC⁰ circuit — no matter how many gates, as long as the depth stays constant — can compute parity. More generally, AC⁰ circuits augmented with MOD-p gates for one prime pp cannot compute MOD-q for any different prime qq.

The tool they invented to prove it — approximating Boolean functions by low-degree polynomials over finite fields — became one of the most celebrated techniques in circuit complexity, and it is the first time researchers proved an unconditional separation between two natural circuit classes.

Approximate Parity with Polynomials

The heart of the proof is this: any Boolean function computable by a small AC⁰ circuit can be well approximated by a low-degree polynomial over a finite field. But parity is the polynomial x1⊕x2⊕⋯⊕xnx_1 \oplus x_2 \oplus \cdots \oplus x_n — a multilinear polynomial of degree nn — and low-degree polynomials over GF(2) simply cannot match it everywhere.

<p class="hint">Toggle the <b>input bits</b>. The circuit computes <b>MOD-2 (parity)</b>: is the count of 1s even (0) or odd (1)? The <b>best degree-1 polynomial over F₃</b> (mod 3) tries to approximate it — but always misses on some inputs. This gap is the heart of Razborov–Smolensky.</p>
<div class="bit-row" id="bit-row"></div>
<div class="result-grid">
  <div class="result-box">
    <div class="label">MOD-2 (parity)</div>
    <div class="value" id="true-parity">—</div>
  </div>
  <div class="result-box approx">
    <div class="label">Best F₃ degree-1 approx</div>
    <div class="value" id="approx-val">—</div>
  </div>
  <div class="result-box">
    <div class="label">Match?</div>
    <div class="value" id="match-val">—</div>
  </div>
</div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="btn-all" type="button">Show all 16 inputs</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="all-table" style="display:none">
  <p class="table-hint">All <b id="total-inputs"></b> inputs — best F₃ linear approx agrees on <b id="agree-count"></b> (<b id="agree-rate"></b>) — theorem bound: ≤67%</p>
  <div id="table-body" class="table-wrap"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.bit-row { display: flex; gap: 6px; margin-bottom: .8rem; flex-wrap: wrap; }
.bit-btn { width: 44px; height: 44px; border-radius: 8px; border: 2px solid #adb1b8;
           background: #d8dce0; font: 700 18px ui-monospace,monospace; cursor: pointer;
           transition: all .12s; display: flex; align-items: center; justify-content: center;
           color: #333; }
.bit-btn.on { background: #1d3557; border-color: #1d3557; color: #fff; }
.bit-btn:hover { filter: brightness(1.08); }
.result-grid { display: flex; gap: 8px; margin-bottom: .7rem; flex-wrap: wrap; }
.result-box { flex: 1; min-width: 90px; background: #e8eef3; border-radius: 10px;
              padding: .5rem .7rem; text-align: center; border: 1px solid #cdd9e3; }
.result-box.approx { background: #fff3cd; border-color: #e8c84a; }
.label { font-size: .72rem; color: #556; text-transform: uppercase; letter-spacing: .04em; }
.value { font: 700 1.6rem ui-monospace,monospace; margin-top: .15rem; }
.value.agree { color: #0a7d33; }
.value.disagree { color: #c92f3c; }
.status { font-size: .88rem; font-weight: 600; min-height: 1.3em; margin-bottom: .5rem; color: #444; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 13px system-ui,sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.table-hint { font-size: .85rem; color: #444; margin: 0 0 .4rem; }
.table-wrap { overflow-x: auto; }
table { border-collapse: collapse; font-size: .82rem; width: 100%; }
th { background: #e8eef3; padding: .3rem .5rem; text-align: center; border: 1px solid #cdd9e3;
     font-size: .72rem; text-transform: uppercase; letter-spacing: .04em; }
td { padding: .25rem .5rem; text-align: center; border: 1px solid #e0e4e8;
     font-family: ui-monospace,monospace; }
tr.agree-row td { background: #f0faf4; }
tr.disagree-row td { background: #fff5f5; }
.poly-desc { font-size: .82rem; color: #556; margin-bottom: .5rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Razborov-Smolensky demo
// -------------------------
// The theorem: AC0[p] circuits (AND/OR + MOD-p gates, constant depth) cannot compute MOD-q for a DIFFERENT prime q.
//
// Proof idea (Smolensky 1987):
//   1. Every AC0[p] circuit can be approximated by a LOW-DEGREE polynomial over F_p.
//   2. MOD-q is NOT well-approximated by any low-degree polynomial over F_p.
//   3. Therefore no AC0[p] circuit can compute MOD-q.
//
// Demo: we fix p=3, q=2 (MOD-2 = parity, target; F_3 = integers mod 3).
// We find the BEST degree-1 polynomial over F_3 that approximates parity on n=4 binary inputs. The theorem guarantees it misses at least 1/3 of all inputs.
//
// A degree-1 poly over F_3: f(x) = c0 + c1*x1 + c2*x2 + c3*x3 + c4*x4  (mod 3)
// with each coefficient c_i in {0,1,2}.
// We compare f(x) mod 3 to parity(x) in {0,1} ⊆ F_3.

const N = 4;        // number of input bits
const P = 3;        // field characteristic (F_3)
const TOTAL = 1 << N; // 16 inputs

function mod3(x) { return ((x % P) + P) % P; }
function trueParity(bv) { return bv.reduce((a, b) => a ^ b, 0); }
function evalLinearF3(coeffs, bv) {
  let v = coeffs[0];
  for (let i = 0; i < N; i++) v = mod3(v + coeffs[i + 1] * bv[i]);
  return v;
}
function intToBits(inp) {
  const bv = [];
  for (let i = 0; i < N; i++) bv.push((inp >> i) & 1);
  return bv;
}

// Precompute: find the best degree-1 polynomial over F_3 approximating MOD-2
// Enumerate all 3^(N+1) such polynomials
function findBestLinearF3() {
  let bestCoeffs = null, bestAgree = -1;
  // Generate all coefficient vectors in F_3^(N+1)
  const numCoeffs = N + 1;
  const total = Math.pow(P, numCoeffs); // 3^5 = 243
  for (let mask = 0; mask < total; mask++) {
    const coeffs = [];
    let m = mask;
    for (let i = 0; i < numCoeffs; i++) { coeffs.push(m % P); m = Math.floor(m / P); }
    let agree = 0;
    for (let inp = 0; inp < TOTAL; inp++) {
      const bv = intToBits(inp);
      if (evalLinearF3(coeffs, bv) === trueParity(bv)) agree++;
    }
    if (agree > bestAgree) { bestAgree = agree; bestCoeffs = coeffs.slice(); }
  }
  return { coeffs: bestCoeffs, agree: bestAgree };
}

const { coeffs: BEST, agree: BEST_AGREE } = findBestLinearF3();

// Describe the polynomial
function describeF3Poly(coeffs) {
  const sym = ['0', '1', '2'];
  const terms = [];
  if (coeffs[0] !== 0) terms.push(sym[coeffs[0]]);
  for (let i = 0; i < N; i++) {
    if (coeffs[i + 1] !== 0) {
      terms.push((coeffs[i+1] === 1 ? '' : sym[coeffs[i+1]] + '·') + 'x' + (i + 1));
    }
  }
  return (terms.length ? terms.join(' + ') : '0') + '  (mod 3)';
}

const POLY_DESC = describeF3Poly(BEST);
const bits = new Array(N).fill(0);

// Verify the theorem guarantee holds
console.assert(BEST_AGREE < TOTAL,
  'BUG: best linear F3 poly should not perfectly approximate parity');
console.assert(BEST_AGREE <= Math.ceil(TOTAL * (P - 1) / P),
  'BUG: agreement should be at most (p-1)/p fraction');
console.log('Best degree-1 F3 poly agrees on', BEST_AGREE, '/', TOTAL,
  fmt('(%round%%) — theorem bound: ≤%round2%% — PASS', { round: Math.round(100 * BEST_AGREE / TOTAL), round2: Math.round(100 * (P-1) / P) }));

function render() {
  const row = document.getElementById('bit-row');
  row.innerHTML = '';
  for (let i = 0; i < N; i++) {
    const btn = document.createElement('button');
    btn.className = 'bit-btn' + (bits[i] ? ' on' : '');
    btn.textContent = bits[i];
    btn.title = 'x' + (i + 1) + ' = ' + bits[i];
    btn.addEventListener('click', () => { bits[i] ^= 1; render(); updateResults(); });
    row.appendChild(btn);
  }
}

function updateResults() {
  const tp = trueParity(bits);
  const ap = evalLinearF3(BEST, bits);
  const match = tp === ap;

  document.getElementById('true-parity').textContent = tp;
  document.getElementById('approx-val').textContent = ap;

  const mEl = document.getElementById('match-val');
  mEl.className = 'value ' + (match ? 'agree' : 'disagree');
  mEl.textContent = match ? '✓' : '✗';

  const sEl = document.getElementById('status');
  if (match) {
    sEl.textContent = '✓ Polynomial agrees with parity on this input.';
    sEl.className = 'status ok';
  } else {
    sEl.textContent = fmt('✗ Polynomial gives %ap%  but parity is %tp% — a miss.', { ap: ap, tp: tp });
    sEl.className = 'status bad';
  }
}

function buildTable() {
  const headers = ['#', 'x₁', 'x₂', 'x₃', 'x₄', 'MOD-2', 'F₃ approx', 'Match'];
  let html = '<table><thead><tr>' + headers.map(h => '<th>' + h + '</th>').join('') + '</tr></thead><tbody>';
  for (let inp = 0; inp < TOTAL; inp++) {
    const bv = intToBits(inp);
    const tp = trueParity(bv);
    const ap = evalLinearF3(BEST, bv);
    const match = tp === ap;
    html += '<tr class="' + (match ? 'agree-row' : 'disagree-row') + '">';
    html += '<td>' + inp + '</td>';
    bv.forEach(b => { html += '<td>' + b + '</td>'; });
    html += '<td>' + tp + '</td>';
    html += '<td>' + ap + '</td>';
    html += '<td>' + (match ? '✓' : '✗') + '</td>';
    html += '</tr>';
  }
  html += '</tbody></table>';
  return html;
}

let tableOpen = false;
document.getElementById('btn-all').addEventListener('click', () => {
  tableOpen = !tableOpen;
  const el = document.getElementById('all-table');
  el.style.display = tableOpen ? 'block' : 'none';
  document.getElementById('btn-all').textContent = tableOpen ? 'Hide table' : 'Show all 16 inputs';
  if (tableOpen) {
    document.getElementById('total-inputs').textContent = TOTAL;
    document.getElementById('agree-count').textContent = BEST_AGREE + '/' + TOTAL;
    document.getElementById('agree-rate').textContent = Math.round(100 * BEST_AGREE / TOTAL) + '%';
    document.getElementById('table-body').innerHTML = buildTable();
  }
});

document.getElementById('btn-reset').addEventListener('click', () => {
  bits.fill(0);
  tableOpen = false;
  document.getElementById('all-table').style.display = 'none';
  document.getElementById('btn-all').textContent = 'Show all 16 inputs';
  render();
  updateResults();
});

// Show polynomial description
const polyEl = document.createElement('div');
polyEl.className = 'poly-desc';
polyEl.innerHTML = fmt('Best approximation: <b>f(x) = %POLY_DESC%</b>', { POLY_DESC: POLY_DESC });
document.querySelector('.result-grid').insertAdjacentElement('afterend', polyEl);
document.querySelector('.status').insertAdjacentElement('beforebegin', polyEl);

render();
updateResults();
Result
Console

Toggle the input bits and watch how the degree-1 polynomial (the best linear approximation) compares to true parity. It agrees on most inputs — but always fails on some. Click Show all inputs to see every case: no linear function over GF(2) matches parity on more than 75 % of the 2n2^n inputs when n≥2n \geq 2. This gap is exactly what the Razborov–Smolensky argument formalizes.

The Real Complexity

The Razborov–Smolensky theorem is one of the few provable, unconditional lower bounds in complexity theory. Here is the argument in outline:

  • Step 1 — Polynomials approximate gates. Over a field Fp\mathbb{F}_p, AND and OR gates of fan-in kk can each be replaced by a polynomial of degree at most kk. Composing dd layers yields a polynomial of degree at most sds^d, where ss is the fan-in.
  • Step 2 — Restrict the input randomly. Randomly set each variable to 0 or 1 independently with some probability. The surviving polynomial has low expected degree: for a depth-dd circuit of size SS, it lands in degree O(log⁡S)dO(\log S)^d with high probability.
  • Step 3 — Parity (MOD 2) is degree nn over any field. To exactly compute parity, the polynomial must have degree nn — it cannot be compressed. The same is true for MOD-q when q≠pq \neq p.
  • Step 4 — Low degree means high error. A polynomial of degree much less than nn over Fp\mathbb{F}_p agrees with MOD-q on at most a 1−1/p1 - 1/p fraction of inputs. If the circuit correctly computed MOD-q, its approximating polynomial would have to agree everywhere — contradiction.

The conclusion: any AC⁰[p] circuit computing MOD-q must have size 2nΩ(1)2^{n^{\Omega(1)}} — exponential in a power of the input length. This is a proven impossibility, not a conjecture like P vs NP.

The theorem was proved independently by Razborov (1987) using the method of approximations and by Smolensky (1987) using the cleaner polynomial representation over Fp\mathbb{F}_p. Together they closed a question that had been open since the rise of circuit complexity.

Where It Matters

The Razborov–Smolensky result did more than settle a single question — it launched an entire methodology:

  • Circuit lower bounds: the polynomial method is the template for proving that natural functions require large circuits. It directly inspired the approach behind counting #P hardness proofs and later algebraic methods.
  • Pseudorandomness: low-degree polynomials over finite fields are the building blocks of many pseudorandom generators. Understanding their limits is essential to constructing generators that fool AC⁰[p] circuits.
  • Learning theory: the Kushilevitz–Mansour theorem (1993) showed that AC⁰ functions are learnable from their Fourier spectrum — a direct consequence of the low-degree structure the Razborov–Smolensky proof reveals.
  • Cryptography: many constructions of hash functions and error-correcting codes rely on the hardness of computing MOD functions cheaply. The theorem provides the theoretical backbone.
  • Complexity separations: it remains the only known unconditional separation of circuit complexity classes that goes beyond depth-2 circuits, making it a cornerstone reference whenever researchers ask what shallow computation can and cannot do.

The proof technique itself — replace gates by polynomials, apply a random restriction, count degrees — reappears throughout modern complexity theory and has been called one of the "top ten" ideas in the field.

Conclusion

The Razborov–Smolensky theorem is a rarity in complexity theory: an unconditional, provable lower bound on what shallow circuits can do. No constant-depth circuit of AND, OR, and MOD-p gates — however large — can tell whether the count of 1s in an input is divisible by a different prime qq.

The polynomial method that powers the proof has since become a standard lens for understanding computation: represent gates as polynomials, track degree under random restrictions, and watch the gap between what circuits can express and what the target function demands.

Most of the big questions in complexity — including P vs NP itself — remain wide open. Razborov–Smolensky stands as one of the few places where the curtain has actually been pulled back, revealing that some computations are genuinely, provably beyond the reach of a natural model. That is a rare and beautiful thing.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

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