Introduction

Imagine you have not one computer but a million working in perfect synchrony. Which problems suddenly become fast, and which stay stubbornly slow no matter how many processors you throw at them?

That question is captured by two complexity classes. P is the set of problems solvable in polynomial time on a single processor — roughly, everything "efficiently computable" by today's computers. NC (Nick's Class, named after Nick Pippenger) is the set of problems solvable in polylogarithmic time — O(log⁡kn)O(\log^k n) for some constant kk — using a polynomial number of processors working in parallel. These are the problems that can be finished in a tiny number of parallel steps even for huge inputs.

It is clear that NC⊆P\text{NC} \subseteq \text{P}: anything that finishes in O(log⁡kn)O(\log^k n) parallel steps also finishes in polynomial sequential time. But does every polynomial-time algorithm admit a parallel speedup that dramatic? That is NC vs P: still open, as of 2026, with no proof in either direction.

The question matters far beyond theory: it is asking whether the age of massively parallel hardware — GPUs, datacenters, neural-network accelerators — gives us a fundamentally different kind of speed, or only a constant-factor advantage for the hardest problems.

Race: Sequential vs Parallel

Adding up an array is a clean example. Sequentially you visit every element one by one: nn steps. In parallel you can use a prefix-sum tree — double the stride each round, finish in O(log⁡n)O(\log n) rounds no matter how many elements there are.

<p class="hint">
  Choose an array size, then run both approaches. Sequential visits elements one by one — <b>n steps</b>. Parallel prefix-sum uses a tree of doublings — <b>⌈log₂ n⌉ rounds</b>.
</p>
<div class="controls">
  <label>Array size: <select id="sizeSelect">
    <option value="4">4</option>
    <option value="8" selected>8</option>
    <option value="16">16</option>
    <option value="32">32</option>
    <option value="64">64</option>
  </select></label>
  <button id="btnSeq" type="button">▶ Run sequential</button>
  <button id="btnPar" type="button">▶ Run parallel</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<div id="arrayViz" class="array-viz"></div>
<div id="treeViz" class="tree-viz"></div>
<div id="statsBox" class="stats-box">
  <span id="statSeq" class="stat">Sequential steps: —</span>
  <span id="statPar" class="stat">Parallel rounds: —</span>
</div>
<div class="status" id="status">Pick a size and run an algorithm.</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; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem; align-items: center; margin-bottom: .8rem; }
label { font-size: .9rem; }
select { font-size: .9rem; border: 1px solid #adb1b8; border-radius: 6px; padding: .2rem .4rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.array-viz { display: flex; flex-wrap: wrap; gap: 4px; margin-bottom: .5rem; }
.cell { min-width: 36px; height: 36px; display: flex; align-items: center;
        justify-content: center; font: 600 13px ui-monospace, monospace;
        border-radius: 6px; border: 1px solid #cdd9e3; background: #e8eef3;
        color: #1d3557; transition: background .3s; }
.cell.active { background: #f4a261; border-color: #e07b3c; color: #fff; }
.cell.done { background: #2a9d8f; border-color: #1e7b6d; color: #fff; }
.tree-viz { font-size: .78rem; color: #555; margin-bottom: .5rem; min-height: 1.2em; }
.tree-viz .round { margin: .15rem 0; }
.tree-viz .round-label { font-weight: 700; color: #1d3557; margin-right: .4rem; }
.stats-box { display: flex; gap: 1.2rem; flex-wrap: wrap; margin-bottom: .4rem; }
.stat { font-size: .9rem; font-weight: 600; }
#statSeq { color: #e63946; }
#statPar { color: #0a7d33; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// NC vs P demo: compare sequential summation (n steps) vs
// parallel prefix-sum (ceil(log2 n) rounds, each touching n/2 pairs).
// This illustrates why prefix-sum is in NC: O(log n) depth, O(n) work.

let arr = [], n = 8;
let animTimer = null;

function randomArr(size) {
  return Array.from({ length: size }, () => Math.floor(Math.random() * 9) + 1);
}

function resetAll() {
  if (animTimer) { clearTimeout(animTimer); animTimer = null; }
  n = parseInt(document.getElementById('sizeSelect').value, 10);
  arr = randomArr(n);
  document.getElementById('statSeq').textContent = 'Sequential steps: —';
  document.getElementById('statPar').textContent = 'Parallel rounds: —';
  document.getElementById('status').textContent = 'Pick a size and run an algorithm.';
  document.getElementById('status').className = 'status';
  document.getElementById('treeViz').innerHTML = '';
  renderArray(arr, []);
}

function renderArray(values, highlighted) {
  const viz = document.getElementById('arrayViz');
  viz.innerHTML = '';
  values.forEach((v, i) => {
    const d = document.createElement('div');
    d.className = 'cell' + (highlighted.includes(i) ? ' active' : '');
    d.textContent = v;
    viz.appendChild(d);
  });
}

function markDone(indices) {
  const cells = document.getElementById('arrayViz').querySelectorAll('.cell');
  indices.forEach(i => { if (cells[i]) cells[i].className = 'cell done'; });
}

// Sequential: animate visiting each index, accumulating sum
function runSequential() {
  if (animTimer) { clearTimeout(animTimer); animTimer = null; }
  resetAll();
  let step = 0, acc = arr[0];
  renderArray(arr, [0]);
  markDone([0]);
  document.getElementById('statSeq').textContent = fmt('Sequential steps: 1 / %n%', { n: n });
  document.getElementById('status').textContent = fmt('Running sequential… step 1 of %n%, running sum = %acc%', { n: n, acc: acc });

  function tick() {
    step++;
    if (step >= n) {
      document.getElementById('statSeq').textContent = fmt('Sequential steps: %n%', { n: n });
      document.getElementById('status').textContent = fmt('Sequential done: sum = %acc% in %n% steps.', { acc: acc, n: n });
      document.getElementById('status').className = 'status ok';
      renderArray(arr, []);
      markDone(arr.map((_, i) => i));
      return;
    }
    acc += arr[step];
    renderArray(arr, [step]);
    // Re-mark done
    const cells = document.getElementById('arrayViz').querySelectorAll('.cell');
    for (let i = 0; i < step; i++) { if (cells[i]) cells[i].className = 'cell done'; }
    document.getElementById('statSeq').textContent = fmt('Sequential steps: %v% / %n%', { v: step + 1, n: n });
    document.getElementById('status').textContent = fmt('Running sequential… step %v% of %n%, running sum = %acc%', { v: step + 1, n: n, acc: acc });
    animTimer = setTimeout(tick, 400);
  }
  animTimer = setTimeout(tick, 400);
}

// Parallel prefix-sum (Blelloch up-sweep) animated by rounds.
// In round r (stride = 2^r), the right child of each pair is at
// index i = stride*2 - 1, stride*4 - 1, … (i.e. i starts at stride*2-1,
// step stride*2). work[i] += work[i - stride].
function runParallel() {
  if (animTimer) { clearTimeout(animTimer); animTimer = null; }
  resetAll();
  const rounds = Math.ceil(Math.log2(n));
  const treeDiv = document.getElementById('treeViz');
  treeDiv.innerHTML = '';
  // Build rounds list using the correct Blelloch up-sweep indices.
  const roundPairs = [];
  for (let r = 0; r < rounds; r++) {
    const stride = 1 << r;
    const pairs = [];
    for (let i = stride * 2 - 1; i < n; i += stride * 2) {
      pairs.push([i - stride, i]);
    }
    roundPairs.push(pairs);
  }

  // Build working array (we show prefix sums building up)
  const work = arr.slice();
  let roundIdx = 0;

  function doRound() {
    if (roundIdx >= rounds) {
      document.getElementById('statPar').textContent = fmt('Parallel rounds: %rounds% (log₂ %n% = %rounds%)', { rounds: rounds, n: n });
      document.getElementById('status').textContent = fmt('Parallel done: %rounds% rounds — total sum = %v%.', { rounds: rounds, v: work[n - 1] });
      document.getElementById('status').className = 'status ok';
      renderArray(work, []);
      markDone(work.map((_, i) => i));
      return;
    }
    const stride = 1 << roundIdx;
    const pairs = roundPairs[roundIdx];
    // Show active cells
    const active = pairs.flatMap(([a, b]) => [a, b]);
    renderArray(work, active);
    // Apply sums
    pairs.forEach(([a, b]) => { work[b] = work[a] + work[b]; });

    // Log round
    const rowEl = document.createElement('div');
    rowEl.className = 'round';
    rowEl.innerHTML = fmt('<span class="round-label">Round %v% (stride %stride%):</span>%map%', { v: roundIdx + 1, stride: stride, map: pairs.map(([a, b]) => `[${a}]+[${b}]`).join('  ') });
    treeDiv.appendChild(rowEl);

    document.getElementById('statPar').textContent = fmt('Parallel rounds: %v% / %rounds%', { v: roundIdx + 1, rounds: rounds });
    document.getElementById('status').textContent = fmt('Round %v% of %rounds% — combining %length% pair(s) simultaneously.', { v: roundIdx + 1, rounds: rounds, length: pairs.length });

    roundIdx++;
    animTimer = setTimeout(doRound, 700);
  }

  renderArray(arr, []);
  document.getElementById('status').textContent = fmt('Starting parallel prefix-sum on %n% elements…', { n: n });
  animTimer = setTimeout(doRound, 500);
}

document.getElementById('sizeSelect').addEventListener('change', resetAll);
document.getElementById('btnSeq').addEventListener('click', runSequential);
document.getElementById('btnPar').addEventListener('click', runParallel);
document.getElementById('btnReset').addEventListener('click', resetAll);

// Verify: parallel prefix-sum (Blelloch up-sweep) must yield same total as sequential.
(function selfTest() {
  const testArr = [3, 1, 4, 1, 5, 9, 2, 6];
  const seqSum = testArr.reduce((a, b) => a + b, 0);
  const work = testArr.slice();
  const n2 = testArr.length;
  const rounds2 = Math.ceil(Math.log2(n2));
  for (let r = 0; r < rounds2; r++) {
    const stride = 1 << r;
    // Right child is at stride*2-1, stride*4-1, … (Blelloch up-sweep)
    for (let i = stride * 2 - 1; i < n2; i += stride * 2) {
      work[i] = work[i - stride] + work[i];
    }
  }
  if (work[n2 - 1] !== seqSum) {
    console.error('Self-test FAILED: expected', seqSum, 'got', work[n2 - 1]);
  } else {
    console.log('Self-test passed: parallel prefix-sum total =', work[n2 - 1]);
  }
})();

resetAll();
Result
Console

Notice that the parallel depth (rounds) grows only as log⁡2n\log_2 n while sequential steps grow linearly. Prefix-sum is in NC: the depth is polylogarithmic and you only need O(n)O(n) processors. Contrast this with problems suspected to be P-complete — like circuit-value evaluation — where the best known parallel algorithms still require depth proportional to the input size. Those are the potential witnesses that NC≠P\text{NC} \neq \text{P}.

The Real Complexity

Here is the precise picture — and what makes the question so hard:

  • NC is defined via PRAM (Parallel Random-Access Machine) models or equivalently via Boolean circuit families with polynomial size and O(log⁡kn)O(\log^k n) depth. Both definitions yield the same class.
  • NC ⊆ P is proven: a circuit of depth dd and polynomial size can be simulated sequentially in O(nk)O(n^k) steps by evaluating gates level by level.
  • P-completeness is the key concept. A problem is P-complete (under log-space reductions) if every problem in P reduces to it. The canonical example is Circuit Value Problem (CVP): given a Boolean circuit and its inputs, what is the output? CVP is in P (evaluate gate by gate), but every known parallel algorithm for it has depth Ω(n)\Omega(n) — linear, not polylogarithmic.
  • The open question: is CVP (and every P-complete problem) outside NC? If yes, NC≠P\text{NC} \neq \text{P}. If no, NC=P\text{NC} = \text{P}. Nobody knows. Proving NC≠P\text{NC} \neq \text{P} would require showing a circuit lower bound — a task that has resisted decades of effort, blocked by barriers like Natural Proofs (Razborov & Rudich, 1997) and Algebrization (Aaronson & Wigderson, 2009).
  • Relation to P vs NP: NC vs P is an independent question. Even if P=NP\text{P} = \text{NP}, it would not immediately resolve NC vs P. And even if NC=P\text{NC} = \text{P}, it would not collapse NP into P.

The status: open. NC vs P is widely believed to have NC≠P\text{NC} \neq \text{P} — meaning some inherently sequential problems exist — but this remains unproven.

Where It Matters

NC vs P is not abstract: it directly governs the limits of every massively parallel system we build.

  • GPU computing and deep learning: matrix multiplication, convolutions, and sorting are all in NC — that is why GPUs give enormous speedups for them. Problems outside NC could not be accelerated the same way no matter how many CUDA cores you add.
  • Database query evaluation: many relational queries are NC-parallel (e.g., joins on sorted data), but evaluating recursive queries can be P-complete. Understanding the boundary guides query optimizer design.
  • Cryptography: some cryptographic primitives are intentionally P-complete or harder to resist parallel brute force. The answer to NC vs P would clarify exactly how much parallelism helps an attacker.
  • Program analysis: dataflow analysis and compiler optimizations often reduce to variants of CVP. Their inherent parallelizability is an open research question with direct impact on compiler technology.
  • Scientific computing: differential equation solvers, graph algorithms (like maximum matching), and linear programming all live near the NC/P boundary. Results here guide supercomputer algorithm design.

Conclusion

NC vs P sits at the intersection of theoretical computer science and the engineering of every parallel system ever built. NC captures the idea of "embarrassingly parallelizable" — finish in a few logarithmic rounds with enough processors. P captures "efficiently computable" by any means. The question is whether those two ideas coincide.

Everything we know says they probably don't: P-complete problems like Circuit Value appear to need linear depth no matter how many processors you use. But proving it requires circuit lower bounds that have eluded researchers for over four decades, guarded by deep barriers in proof complexity.

So the next time a GPU advertisement promises to make everything faster, remember: there may be a mathematical wall that no amount of parallelism can cross. Whether that wall really exists is one of the most beautiful unresolved questions in all of computer science — hiding in plain sight, every time you compile a program or run a neural network. See also P vs NP for the related question of verification versus discovery.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/nc-vs-p/Content licensed under CC BY-NC 4.0.