NC vs P

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^k n)$ for some constant $k$ — 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 $\text{NC} \subseteq \text{P}$: anything that finishes in $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.

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

<p class="hint">
  {{hint}}
</p>
<div class="controls">
  <label>{{array_size_label}} <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">{{btn_seq}}</button>
  <button id="btnPar" type="button">{{btn_par}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_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">{{stat_seq_init}}</span>
  <span id="statPar" class="stat">{{stat_par_init}}</span>
</div>
<div class="status" id="status">{{status_init}}</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; }

// Code not found

Notice that the parallel depth (rounds) grows only as $\log_2 n$ while sequential steps grow linearly. Prefix-sum is in NC: the depth is polylogarithmic and you only need $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 $\text{NC} \neq \text{P}$.

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^k n)$ depth. Both definitions yield the same class.
• NC ⊆ P is proven: a circuit of depth $d$ and polynomial size can be simulated sequentially in $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 $\Omega(n)$ — linear, not polylogarithmic.
• The open question: is CVP (and every P-complete problem) outside NC? If yes, $\text{NC} \neq \text{P}$. If no, $\text{NC} = \text{P}$. Nobody knows. Proving $\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 $\text{P} = \text{NP}$, it would not immediately resolve NC vs P. And even if $\text{NC} = \text{P}$, it would not collapse NP into P.

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

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.

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.