Introduction

Write down the formula for the determinant of an n×nn \times n matrix and the formula for its permanent. They are almost the same object: both are a sum over all n!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!n! terms, Gaussian elimination computes it with about n3n^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.

Try It

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 n3n^3 steps. The permanent is computed the honest way, summing over permutations — n!n! terms.

<p class="hint">Pick a matrix size, enter or randomize small integers, then compute <b>both</b> its determinant and its permanent. They sum over the very same permutations — only the signs differ — yet one stays cheap while the other's work explodes.</p>
<div class="controls">
  <label class="sizelbl">Matrix size:
    <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">Randomize</button>
</div>
<div id="matrix" class="matrix"></div>
<div class="btns">
  <button id="compute" type="button">Compute both</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="cards">
  <div class="card det">
    <div class="cap">Determinant (easy · VP)</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">Permanent (hard · VNP)</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">Same formula shape: pick one entry per row and column, multiply, add. Only the signs change.</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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Determinant vs permanent: identical sums over the n! permutations of columns.
// The determinant weights each term by the sign of the permutation (+/-); the permanent adds them all with a plus.
let N = 3;

// Determinant via fraction-free (Bareiss-style) Gaussian elimination: about n^3 operations.
// This is why the determinant lives in VP despite its n!-term definition.
function determinant(M){
  const n = M.length;
  const a = M.map(row => row.slice());
  let sign = 1, ops = 0, prev = 1;
  for (let k = 0; k < n; k++){
    if (a[k][k] === 0){
      let sw = -1;
      for (let i = k + 1; i < n; i++) if (a[i][k] !== 0){ sw = i; break; }
      if (sw === -1) return { value: 0, ops };
      const t = a[k]; a[k] = a[sw]; a[sw] = t; sign = -sign;
    }
    for (let i = k + 1; i < n; i++){
      for (let j = k + 1; j < n; j++){
        a[i][j] = (a[i][j] * a[k][k] - a[i][k] * a[k][j]) / prev;
        ops++;
      }
    }
    prev = a[k][k];
  }
  return { value: sign * a[n - 1][n - 1], ops };
}

// Permanent the honest way: sum the product over every permutation of columns.
// That is n! terms - the work explodes and is conjectured to require super-polynomial circuits (VP != VNP).
function permanent(M){
  const n = M.length;
  const cols = [];
  for (let i = 0; i < n; i++) cols.push(i);
  let total = 0, terms = 0;
  const perm = (arr, k) => {
    if (k === arr.length){
      let prod = 1;
      for (let r = 0; r < n; r++) prod *= M[r][arr[r]];
      total += prod; terms++;
      return;
    }
    for (let i = k; i < arr.length; i++){
      [arr[k], arr[i]] = [arr[i], arr[k]];
      perm(arr, k + 1);
      [arr[k], arr[i]] = [arr[i], arr[k]];
    }
  };
  perm(cols, 0);
  return { value: total, terms };
}

function factorial(n){ let f = 1; for (let i = 2; i <= n; i++) f *= i; return f; }

function buildMatrix(){
  const wrap = document.getElementById('matrix');
  wrap.style.gridTemplateColumns = 'repeat(' + N + ', 46px)';
  wrap.innerHTML = '';
  for (let r = 0; r < N; r++) for (let c = 0; c < N; c++){
    const inp = document.createElement('input');
    inp.type = 'number';
    inp.value = String(Math.floor(Math.random() * 9) - 2);
    inp.dataset.r = r; inp.dataset.c = c;
    wrap.appendChild(inp);
  }
}

function readMatrix(){
  const M = Array.from({ length: N }, () => new Array(N).fill(0));
  document.querySelectorAll('#matrix input').forEach(inp => {
    const v = parseInt(inp.value, 10);
    M[+inp.dataset.r][+inp.dataset.c] = Number.isFinite(v) ? v : 0;
  });
  return M;
}

function compute(){
  const M = readMatrix();
  const det = determinant(M);
  const per = permanent(M);
  const nCube = N * N * N;
  const nFact = factorial(N);
  document.getElementById('detVal').textContent = String(det.value);
  document.getElementById('permVal').textContent = String(per.value);
  document.getElementById('detCost').textContent =
    i18nFmt('About n^3 = %ops% operations (Gaussian elimination).', { n: N, ops: nCube });
  document.getElementById('permCost').textContent =
    i18nFmt('n! = %terms% permutation terms (brute sum).', { n: N, terms: nFact });
  const maxFact = factorial(4);
  document.getElementById('detBar').style.width =
    Math.min(100, (nCube / (4 * 4 * 4)) * 100) + '%';
  document.getElementById('permBar').style.width =
    Math.min(100, (nFact / maxFact) * 100) + '%';
  document.getElementById('note').textContent =
    i18nFmt('The determinant needed about %cheap% operations; the permanent summed %boom% terms. Same shape, wildly different cost.', { cheap: nCube, boom: nFact });
  // Report the two values and the permanent's term count to the console.
  console.log(i18nFmt('det = %d% | perm = %p% (summed %terms% permutation terms)', { d: det.value, p: per.value, terms: nFact }));
}

document.getElementById('size').addEventListener('change', (e) => {
  N = parseInt(e.target.value, 10); buildMatrix();
});
document.getElementById('rand').addEventListener('click', buildMatrix);
document.getElementById('compute').addEventListener('click', compute);
document.getElementById('reset').addEventListener('click', () => {
  buildMatrix();
  document.getElementById('detVal').innerHTML = '&mdash;';
  document.getElementById('permVal').innerHTML = '&mdash;';
  document.getElementById('detCost').innerHTML = '&nbsp;';
  document.getElementById('permCost').innerHTML = '&nbsp;';
  document.getElementById('detBar').style.width = '0';
  document.getElementById('permBar').style.width = '0';
  document.getElementById('note').textContent = 'Same formula shape: pick one entry per row and column, multiply, add. Only the signs change.';
});
buildMatrix();
Result
Console

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 nn 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 Real Complexity

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 (fn)(f_n) that have arithmetic circuits of polynomial size and polynomially bounded degree. The emblematic member is the determinant: despite its n!n!-term definition, it lives in VP thanks to Gaussian elimination and the Berkowitz algorithm, using about n3n^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, fn(x)=∑e∈{0,1}mg(x,e)f_n(x) = \sum_{e \in \{0,1\}^m} g(x, e) for some g∈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 perm⁡\operatorname{perm} is complete for VNP over any field of characteristic ≠2\neq 2: every VNP polynomial reduces to it. It is the algebraic stand-in for an NP-complete problem.
  • Valiant's conjecture: VP≠VNP\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×nn \times n permanent as a single determinant of a matrix of affine linear forms provably needs a matrix of size at least 2Ω(n)2^{\Omega(n)} (Mignon–Ressayre, and later superpolynomial bounds) over characteristic ≠2\neq 2. Those are genuine lower bounds — but only for restricted models. The general VP vs VNP question remains unsolved.

Where It Matters

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.

Conclusion

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 — VP≠VNP\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.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/algebraic-complexity-vp-vnp/Content licensed under CC BY-NC 4.0.