Algebraic Complexity: VP vs VNP

Write down the formula for the determinant of an $n \times n$ matrix and the formula for its permanent. They are almost the same object: both are a sum over all $n!$ ways of picking one entry from each row and column. The only difference is that the determinant sprinkles in alternating $+$ and $-$ signs, while the permanent adds every term with a $+$.

One tiny change in the signs — and the two formulas part ways completely. The determinant is easy: even though its definition has $n!$ terms, Gaussian elimination computes it with about $n^3$ arithmetic operations. The permanent has resisted every attempt at a fast formula, and it is conjectured to require arithmetic circuits of super-polynomial size.

In 1979 Leslie Valiant turned this contrast into a precise question — the algebraic mirror image of P vs NP. He defined two classes of polynomials, VP (the "easy" ones) and VNP (the "verifiable" ones), and asked whether they are truly different. Like its Boolean cousin, VP vs VNP is still open.

Below is a small integer matrix you can edit or randomize. The demo computes both its determinant and its permanent, and shows the work each one takes. The determinant uses fraction-free elimination — roughly $n^3$ steps. The permanent is computed the honest way, summing over permutations — $n!$ terms.

<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label class="sizelbl">{{size_label}}
    <select id="size">
      <option value="2">2 &times; 2</option>
      <option value="3" selected>3 &times; 3</option>
      <option value="4">4 &times; 4</option>
    </select>
  </label>
  <button id="rand" type="button">{{btn_random}}</button>
</div>
<div id="matrix" class="matrix"></div>
<div class="btns">
  <button id="compute" type="button">{{btn_compute}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="cards">
  <div class="card det">
    <div class="cap">{{det_label}}</div>
    <div class="val" id="detVal">&mdash;</div>
    <div class="cost" id="detCost">&nbsp;</div>
    <div class="bar-wrap"><div class="bar det-bar" id="detBar"></div></div>
  </div>
  <div class="card perm">
    <div class="cap">{{perm_label}}</div>
    <div class="val" id="permVal">&mdash;</div>
    <div class="cost" id="permCost">&nbsp;</div>
    <div class="bar-wrap"><div class="bar perm-bar" id="permBar"></div></div>
  </div>
</div>
<p class="note" id="note">{{note_same_shape}}</p>

* { 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; }
.controls { display: flex; gap: .6rem; align-items: center; flex-wrap: wrap; margin-bottom: .6rem; }
.sizelbl { font-size: .85rem; color: #333; display: flex; gap: .4rem; align-items: center; }
select { font: 600 14px system-ui, sans-serif; padding: .25rem .4rem; border-radius: 6px; border: 1px solid #adb1b8; }
.matrix { display: inline-grid; gap: 4px; margin: .3rem 0 .6rem; }
.matrix input { width: 46px; height: 40px; text-align: center; font: 700 15px ui-monospace, monospace;
                border: 1px solid #cdd9e3; border-radius: 6px; background: #e8eef3; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
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; }
.cards { display: grid; grid-template-columns: 1fr 1fr; gap: .6rem; }
.card { border: 1px solid #cdd9e3; border-radius: 10px; padding: .6rem .7rem; }
.card.perm { border-color: #e0b3b8; }
.cap { font-size: .78rem; font-weight: 700; text-transform: uppercase; letter-spacing: .03em; color: #556; }
.val { font: 700 22px ui-monospace, monospace; margin: .2rem 0; }
.card.det .val { color: #0a7d33; }
.card.perm .val { color: #c92f3c; }
.cost { font-size: .8rem; color: #555; min-height: 1.1em; }
.bar-wrap { height: 10px; background: #eef1f4; border-radius: 6px; overflow: hidden; margin-top: .4rem; }
.bar { height: 100%; width: 0; transition: width .4s ease; }
.det-bar { background: #0a7d33; }
.perm-bar { background: #c92f3c; }
.note { font-size: .82rem; color: #555; line-height: 1.4; margin: .8rem 0 0; }

// Code not found

Notice the shape of both sums is identical: pick one entry per row and column, multiply, add up. Only the signs differ. Yet the operation counter for the permanent blows up as you raise $n$ from 2 to 4, while the determinant's barely moves. That growing gap is a hands-on picture of the VP vs VNP conjecture.

The formal setting swaps bits for algebra. Instead of Turing machines we use arithmetic circuits: directed acyclic graphs whose gates are $+$ and $\times$ over a field.

• VP (Valiant's P) is the class of polynomial families $(f_n)$ that have arithmetic circuits of polynomial size and polynomially bounded degree. The emblematic member is the determinant: despite its $n!$-term definition, it lives in VP thanks to Gaussian elimination and the Berkowitz algorithm, using about $n^3$ operations.
• VNP (Valiant's NP) is the algebraic analogue of NP: a family is in VNP when its coefficients are an efficiently computable exponential sum, $f_n(x) = \sum_{e \in \{0,1\}^m} g(x, e)$ for some $g \in$ VP. Intuitively, VNP polynomials are the ones you can "verify" term by term.
• The permanent is VNP-complete. Valiant's 1979 theorem shows $\operatorname{perm}$ is complete for VNP over any field of characteristic $\neq 2$: every VNP polynomial reduces to it. It is the algebraic stand-in for an NP-complete problem.
• Valiant's conjecture: $\mathrm{VP} \neq \mathrm{VNP}$. Equivalently, the permanent has no polynomial-size arithmetic circuits — it is essentially exponentially harder than the determinant. Widely believed, but open.

Why might this be more tractable than P vs NP? It is a purely algebraic, non-uniform statement, so it sidesteps the relativization and (arguably) the natural-proofs barriers that block the Boolean question, opening the door to tools from algebra and algebraic geometry — most famously Geometric Complexity Theory (Mulmuley–Sohoni), which reframes VP vs VNP as a question about symmetries and orbit closures.

What is actually proven is far more modest. For instance, writing the $n \times n$ permanent as a single determinant of a matrix of affine linear forms provably needs a matrix of size at least $2^{\Omega(n)}$ (Mignon–Ressayre, and later superpolynomial bounds) over characteristic $\neq 2$. Those are genuine lower bounds — but only for restricted models. The general VP vs VNP question remains unsolved.

VP vs VNP is not an isolated curiosity — it sits at the heart of a whole program to understand computation through algebra:

• A cleaner attack on hardness. Because it dodges the relativization and natural-proofs barriers, VP vs VNP is one of the most promising concrete targets for proving a real lower bound — a rehearsal for P vs NP itself.
• Polynomial identity testing (PIT). Deciding whether an arithmetic circuit computes the zero polynomial is a famous problem whose deterministic solution is tightly linked to circuit lower bounds like VP vs VNP.
• Derandomization. Strong lower bounds for arithmetic circuits would let us remove randomness from key algorithms — the algebraic echo of the hardness-vs-randomness theme in circuit complexity.
• Geometric Complexity Theory. The Mulmuley–Sohoni program translates VP vs VNP into deep questions in algebraic geometry and representation theory, connecting complexity to some of the most sophisticated mathematics around.
• Barriers, sharpened. Studying which proof techniques can and cannot separate VP from VNP feeds directly back into the study of natural proofs and the limits of our lower-bound tools.

The permanent also shows up in physics and counting problems, so a resolution would ripple well beyond pure complexity theory.

The determinant and the permanent are the same formula wearing different signs, yet Valiant's conjecture says a chasm separates them: one is easy, the other essentially exponentially hard. That conjecture — $\mathrm{VP} \neq \mathrm{VNP}$, posed in 1979 — is still open.

But it is open in a hopeful way. By living in the world of algebra rather than bits, VP vs VNP escapes some of the barriers that have stalled P vs NP for half a century, and it hands mathematicians a target they can attack with the full machinery of algebraic geometry.

We have proven the permanent hard only in restricted models so far. Whether that hardness holds in full generality is one of the sharpest, most beautiful open questions in all of theoretical computer science — a place where a couple of minus signs may mark the boundary between the tractable and the intractable.