P-Completeness

We know that fast computers can solve many problems efficiently. But can many computers working in parallel solve them faster still?

The class P captures problems solvable in polynomial time on one processor. The class NC (Nick's Class) captures problems solvable in polylogarithmic time with polynomially many parallel processors — roughly, the problems that genuinely benefit from parallelism. Since NC ⊆ P, every problem that parallelizes well is already in P.

The open question is whether NC = P. If they are equal, then every efficiently-solvable problem can be parallelized. If they differ, there exist problems in P that no amount of extra hardware can meaningfully accelerate. Those hardest-to-parallelize problems in P are called P-complete.

Just as NP-complete problems are the hardest in NP (under polynomial reductions), P-complete problems are the hardest in P under the sharper yardstick of NC reductions — reductions computable in polylogarithmic parallel time. Solving any one of them efficiently in parallel would collapse all of P into NC.

The canonical example is the Circuit Value Problem (CVP): given a Boolean circuit and an input, compute the output. Evaluating a circuit feels sequential — each gate depends on its predecessors — and it has been proven P-complete (Cook, 1985). Another classic is the lexicographically first depth-first search (lex-first DFS) order of a graph, also proven P-complete.

The Circuit Value Problem is the heart of P-completeness. A Boolean circuit is a directed acyclic graph: input nodes carry 0 or 1, and every gate computes AND, OR, or NOT of its predecessors.

The circuit below has a fixed topology. Use the toggles to set the two inputs, then press Evaluate to propagate values gate by gate — one level at a time, just as a sequential processor must.

<p class="hint">{{hint}}</p>
<div class="circuit-wrap">
  <svg id="circuit-svg" viewBox="0 0 460 300" xmlns="http://www.w3.org/2000/svg" aria-label="{{svg_aria}}"></svg>
</div>
<div class="status" id="status">{{initial_status}}</div>
<div class="btns">
  <button id="evaluate" type="button">{{btn_evaluate}}</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; }
.circuit-wrap { background: #f4f7fa; border: 1px solid #dce3ea; border-radius: 10px; padding: 8px; margin-bottom: .6rem; overflow: hidden; }
#circuit-svg { width: 100%; height: auto; display: block; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #334155; }
.status.ok { color: #0a7d33; }
.status.running { color: #1d4ed8; }
.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; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice that each gate must wait for all its predecessors. The evaluation order is a strict topological sort, and that dependency chain is precisely what makes CVP hard to parallelize. With $n$ gates arranged in a chain of depth $n$, even infinitely many processors cannot finish in fewer than $n$ steps — depth is the bottleneck, not breadth.

For comparison, matrix multiplication has depth $O(\log n)$ and lives comfortably in NC. Circuit evaluation with depth $\Theta(n)$ sits in P but, under standard complexity assumptions, not in NC.

What makes a problem P-complete? The formal definition mirrors NP-completeness but uses a finer reduction:

• A problem $L$ is P-complete if $L \in \mathrm{P}$ and every problem in P reduces to $L$ via an NC reduction — a many-one reduction computable in polylogarithmic parallel time.
• Checking a single gate output is trivial: look at the inputs, apply the Boolean operation.
• Evaluating the whole circuit requires following a chain of dependencies that can be $\Theta(n)$ gates deep. Even with unlimited processors you cannot skip the chain.
• It's P-complete. Stephen Cook (1985) proved that CVP is P-complete: any polynomial-time algorithm can be simulated by a uniform circuit family, and evaluating that circuit captures exactly the sequential computation. Every problem in P NC-reduces to CVP.
• Lex-first DFS (computing the DFS tree obtained by always choosing the lexicographically smallest neighbor) was proven P-complete by John Reif (1985). The choice at each step depends on which vertices are already visited — an inherently sequential dependency.
• Linear programming (general LP) is also P-complete, meaning that interior-point methods' sequential nature is not an accident.

These results do not prove P ≠ NC — that remains open, just as P vs NP is open. But they show that if P ≠ NC, then CVP, lex-first DFS and their cousins are the exact problems that separate the two classes.

P-completeness is not just theory — it explains concrete engineering limits:

• Hardware and circuit simulation: simulating a sequential digital circuit gate-by-gate is P-complete. This is why full-chip timing simulation cannot be naively parallelized; the signal must propagate through a long dependency chain.
• Data-flow analysis in compilers: reaching definitions and available expressions are computed by iterating over a control-flow graph. The iteration is P-complete, which is why optimizing compilers spend more sequential time in analysis passes than in any single transformation.
• GPU and SIMD limits: GPUs excel at NC problems (matrix products, FFTs, convolutions). When a workload hits P-complete structure — long sequential chains — adding more cores helps barely at all.
• Linear programming: general LP is P-complete. Parallel LP solvers exist, but they cannot escape the sequential core of the simplex or interior-point iterations.
• Teaching parallel complexity: P-completeness gives students a concrete reason why parallelism has limits within P, complementing the more famous P vs NP question about limits above P.

Understanding P-completeness tells you when to stop buying more processors and start redesigning the algorithm — or accepting that the problem is fundamentally sequential.

P-completeness draws a line inside P: on one side are problems like sorting or matrix multiplication that shrink dramatically when you add processors; on the other are problems like circuit evaluation and lex-first DFS that carry an irreducible sequential core.

Whether that line is absolute — whether P truly differs from NC — is unknown. But the P-complete problems mark exactly where the boundary would fall if it exists. Every time a parallel program hits an unexpected bottleneck, P-completeness is worth checking: you may be staring at a sequential dependency chain that no amount of hardware can shorten.

For the deeper question of whether anything in P resists efficient algorithms at all, see P vs NP. For problems that are hard in a different, counting sense, see #P.