Razborov–Smolensky

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 $p$ cannot compute MOD-q for any different prime $q$.

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.

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 $x_1 \oplus x_2 \oplus \cdots \oplus x_n$ — a multilinear polynomial of degree $n$ — and low-degree polynomials over GF(2) simply cannot match it everywhere.

<p class="hint">{{hint}}</p>
<div class="bit-row" id="bit-row"></div>
<div class="result-grid">
  <div class="result-box">
    <div class="label">{{label_parity}}</div>
    <div class="value" id="true-parity">—</div>
  </div>
  <div class="result-box approx">
    <div class="label">{{label_approx}}</div>
    <div class="value" id="approx-val">—</div>
  </div>
  <div class="result-box">
    <div class="label">{{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">{{btn_show}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="all-table" style="display:none">
  <p class="table-hint">{{table_hint}}</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; }

// Code not found

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 $2^n$ inputs when $n \geq 2$. This gap is exactly what the Razborov–Smolensky argument formalizes.

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 $\mathbb{F}_p$, AND and OR gates of fan-in $k$ can each be replaced by a polynomial of degree at most $k$. Composing $d$ layers yields a polynomial of degree at most $s^d$, where $s$ 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-$d$ circuit of size $S$, it lands in degree $O(\log S)^d$ with high probability.
• Step 3 — Parity (MOD 2) is degree $n$ over any field. To exactly compute parity, the polynomial must have degree $n$ — it cannot be compressed. The same is true for MOD-q when $q \neq p$.
• Step 4 — Low degree means high error. A polynomial of degree much less than $n$ over $\mathbb{F}_p$ agrees with MOD-q on at most a $1 - 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 $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 $\mathbb{F}_p$. Together they closed a question that had been open since the rise of circuit complexity.

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.

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 $q$.

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.