Polynomial Identity Testing

Take an algebraic expression — a product of sums, a determinant of a matrix full of variables, a tangle of brackets stacked pages deep. Multiply everything out and a question appears: is the result identically zero? Not zero for one particular input, but zero for every possible value of every variable.

It sounds like bookkeeping. The trouble is scale. A modest expression like a determinant of an n×n matrix expands into n! terms. For n = 20 that is more terms than there are atoms in a city. You can never write them all down, so you can never just "expand and look."

And yet there is a trick so simple it feels like cheating: don't expand — just plug in random numbers and see what comes out. That one idea turns a seemingly hopeless question into a coin flip. Whether you can do the same thing without the coins is one of the great open problems of computer science.

Below are two expressions. One pair is genuinely equal (their difference is the zero polynomial); the other only looks equal but is not. You cannot tell by staring — so test them the way a computer would: feed in random numbers and compare the outputs.

<p class="hint">{{hint}}</p>
<div class="pick">
  <button id="caseA" type="button" class="sel">{{pair_a}}</button>
  <button id="caseB" type="button">{{pair_b}}</button>
</div>
<div class="poly">
  <div class="side"><span class="lbl">{{lbl_left}}</span><code id="lhs"></code></div>
  <div class="eq">=?</div>
  <div class="side"><span class="lbl">{{lbl_right}}</span><code id="rhs"></code></div>
</div>
<div class="readout" id="readout"></div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="run" type="button">{{btn_run1}}</button>
  <button id="run20" type="button">{{btn_run20}}</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: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.pick { display: flex; gap: .4rem; margin-bottom: .7rem; }
.pick button { font: 600 13px system-ui, sans-serif; padding: .35rem .8rem; border: 1px solid #1d3557;
               background: #fff; color: #1d3557; border-radius: 999px; cursor: pointer; }
.pick button.sel { background: #1d3557; color: #fff; }
.poly { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin: .3rem 0 .6rem; }
.side { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem .7rem; flex: 1 1 200px; }
.lbl { display: block; font-size: .7rem; text-transform: uppercase; letter-spacing: .05em; color: #5a7088; margin-bottom: .2rem; }
code { font: 600 14px ui-monospace, monospace; color: #1d3557; }
.eq { font: 700 18px ui-monospace, monospace; color: #5a7088; }
.readout { font: 600 13px ui-monospace, monospace; color: #333; background: #f3f5f8;
           border-radius: 8px; padding: .5rem .7rem; margin: .3rem 0; line-height: 1.6; min-height: 4.2em; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.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

Each random test that gives matching outputs is weak evidence the two sides are equal. A single test on a non-zero polynomial of degree d over a set of S values has at most a d/|S| chance of being fooled — that is the Schwartz-Zippel lemma (Schwartz and Zippel, 1979-1980). Press Run one test repeatedly and watch the chance of a false "equal" collapse: after k independent tests it is below (d/|S|)ᵏ. Checking by random sampling is almost free; proving equality without any randomness at all is the hard part.

How hard is it to decide whether a polynomial (given as a formula or circuit) is identically zero?

• With randomness it is easy. The Schwartz-Zippel lemma gives a one-line algorithm: evaluate at random points. The error shrinks to nothing after a handful of trials, so PIT sits comfortably in the class coRP (and hence BPP) — the problems efficiently solvable with a coin and a tiny error probability.
• Without randomness, nobody knows. Despite decades of effort, no deterministic polynomial-time algorithm for general PIT is known. Whether one exists is open — it is the canonical problem of derandomization, the quest to remove randomness from efficient algorithms.
• It is deeply connected to the hardest questions. Kabanets and Impagliazzo (2003) proved that a fast deterministic PIT algorithm would force circuit lower bounds — it would prove that some explicit problem cannot be computed by small circuits, exactly the kind of statement at the heart of P vs NP. So derandomizing PIT is not a tidy engineering task; it would crack open barriers we have no idea how to pass.
• Special cases have fallen. Restricted models (read-once formulas, sparse polynomials, certain depth-bounded circuits) do admit deterministic algorithms. The general case remains stubbornly open.

That is the punchline: a problem a child could solve by flipping coins resists every attempt to solve it cleanly. PIT is where the power of randomness — and our ignorance about whether it is truly necessary — comes into sharpest focus.

"Are these two algebraic objects the same?" is a question hiding inside an astonishing range of algorithms, and random evaluation is the universal answer key:

• Perfect matchings: a graph has a perfect matching exactly when a certain symbolic determinant (its Tutte/Edmonds matrix) is not the zero polynomial — checked by random evaluation, the core of fast parallel matching algorithms.
• Primality and number theory: identity-style checks underpin classic randomized primality tests, the warm-up to the deterministic AKS test for primality.
• Interactive proofs and verification: protocols like sum-check and the proof that IP = PSPACE lean on testing polynomial identities at random points — the foundation of modern probabilistically checkable proofs and SNARKs.
• Program and data checking: fingerprinting two large files or two computations by evaluating a polynomial over them detects differences with near-certainty using only a few bytes.

Learn why random evaluation works and you have met one of the most reusable ideas in all of computing — and the open question of whether factoring or any other problem truly needs randomness sits right beside it.

Polynomial identity testing carries a strange double life. Hand it a coin and it is trivial: pick random numbers, compare, repeat until the chance of being fooled is smaller than the chance of your computer being hit by a meteor. Take the coin away and it becomes one of the deepest open problems we have — no efficient deterministic algorithm is known, and finding one would shake the foundations of complexity theory itself.

So the next time randomness feels like a shortcut, remember PIT. It is the clearest evidence that a few random bits can be worth more than any amount of cleverness — and the sharpest reminder that we still do not understand why, or whether the coins were ever truly needed. It is randomness made into a question, sitting just beside P vs NP.