Introduction

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.

Evaluate a Circuit

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">Set the two inputs with the toggles, then press <b>Evaluate</b> to watch the circuit compute gate by gate โ€” one level at a time, just as a sequential processor must.</p>
<div class="circuit-wrap">
  <svg id="circuit-svg" viewBox="0 0 460 300" xmlns="http://www.w3.org/2000/svg" aria-label="Boolean circuit"></svg>
</div>
<div class="status" id="status">Click A or B to toggle, then press Evaluate.</div>
<div class="btns">
  <button id="evaluate" type="button">Evaluate</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Circuit Value Problem (CVP) โ€” the canonical P-complete problem (Cook, 1985).
// Circuit computes XOR(A,B) using 6 gates across 4 sequential levels:
//   Level 1: G1 = NOT A,   G2 = NOT B
//   Level 2: G3 = A AND B, G4 = A OR B
//   Level 3: G5 = NOT G3   (= NOT(A AND B))
//   Level 4: G6 = G4 AND G5  (= (A OR B) AND NOT(A AND B) = XOR)
// Each gate must wait for its predecessors โ€” parallelism cannot skip the chain.

const SVG_NS = 'http://www.w3.org/2000/svg';
const svg = document.getElementById('circuit-svg');

// Gate definitions with layout positions
//  Columns:  inputs=40  L1=130  L2=220  L3=310  L4=380  output=445
const DEFS = {
  G1: { op:'NOT', ins:['A'],      label:'NOT', x:130, y:90  },
  G2: { op:'NOT', ins:['B'],      label:'NOT', x:130, y:210 },
  G3: { op:'AND', ins:['A','B'],  label:'AND', x:220, y:120 },
  G4: { op:'OR',  ins:['A','B'],  label:'OR',  x:220, y:180 },
  G5: { op:'NOT', ins:['G3'],     label:'NOT', x:310, y:120 },
  G6: { op:'AND', ins:['G4','G5'],label:'AND', x:380, y:150 },
};
const LEVELS = [['G1','G2'],['G3','G4'],['G5'],['G6']];
const INP_POS = { A:{ x:40, y:90 }, B:{ x:40, y:210 } };
const OUT_POS  = { x:445, y:150 };
const GW=56, GH=28;

const inputs = { A:1, B:0 };
const vals   = {};

function makeEl(tag, attrs, text) {
  const e = document.createElementNS(SVG_NS, tag);
  for (const [k,v] of Object.entries(attrs)) e.setAttribute(k, v);
  if (text !== undefined) e.textContent = text;
  return e;
}

// Right edge of a node
function rightX(id) {
  if (id === 'A' || id === 'B') return INP_POS[id].x + 20;
  return DEFS[id].x + GW/2;
}
function centerY(id) {
  if (id === 'A' || id === 'B') return INP_POS[id].y;
  return DEFS[id].y;
}

function bezier(x1,y1,x2,y2) {
  const mx = (x1+x2)/2;
  return `M${x1},${y1} C${mx},${y1} ${mx},${y2} ${x2},${y2}`;
}

function colorOf(v) { return v === 1 ? '#16a34a' : v === 0 ? '#dc2626' : '#94a3b8'; }
function bgOf(v)    { return v === 1 ? '#d1fae5' : v === 0 ? '#fee2e2' : '#fff'; }
function fgOf(v)    { return v === 1 ? '#065f46' : v === 0 ? '#991b1b' : '#1d3557'; }

function buildSVG() {
  svg.innerHTML = '';
  const wireLayer = makeEl('g',{}); svg.appendChild(wireLayer);
  const gateLayer = makeEl('g',{}); svg.appendChild(gateLayer);

  // Input nodes (clickable toggles)
  for (const id of ['A','B']) {
    const {x,y} = INP_POS[id];
    const v = inputs[id];
    const grp = makeEl('g', { id:'inp-'+id, style:'cursor:pointer' });
    grp.addEventListener('click', () => { inputs[id] ^= 1; buildSVG(); });
    grp.appendChild(makeEl('rect', { x:x-20, y:y-15, width:40, height:30, rx:6,
      fill:bgOf(v), stroke:colorOf(v), 'stroke-width':1.5 }));
    grp.appendChild(makeEl('text', { x, y:y-3, 'text-anchor':'middle',
      'dominant-baseline':'central',
      style:'font:700 14px ui-monospace,monospace; fill:'+fgOf(v) }, String(v)));
    grp.appendChild(makeEl('text', { x, y:y+11, 'text-anchor':'middle',
      style:'font:600 10px system-ui,sans-serif; fill:#475569' }, id));
    gateLayer.appendChild(grp);
  }

  // Wires from inputs to first gates
  for (const [gid, g] of Object.entries(DEFS)) {
    for (const src of g.ins) {
      const v = vals[src] !== undefined ? vals[src] : undefined;
      const w = makeEl('path', {
        d: bezier(rightX(src), centerY(src), g.x-GW/2, g.y),
        fill:'none', stroke: v !== undefined ? colorOf(v) : '#94a3b8',
        'stroke-width': v !== undefined ? 2 : 1.6,
        id: 'w-'+src+'-'+gid
      });
      wireLayer.appendChild(w);
    }
  }

  // Gate nodes
  for (const [id, g] of Object.entries(DEFS)) {
    const v = vals[id];
    const grp = makeEl('g', { id:'gate-'+id });
    grp.appendChild(makeEl('rect', { x:g.x-GW/2, y:g.y-GH/2, width:GW, height:GH, rx:6,
      fill: v !== undefined ? bgOf(v) : '#fff',
      stroke: v !== undefined ? colorOf(v) : '#1d3557', 'stroke-width':1.5 }));
    grp.appendChild(makeEl('text', { x:g.x, y:g.y-3, 'text-anchor':'middle',
      'dominant-baseline':'central',
      style:'font:700 10px ui-monospace,monospace; fill:'+(v !== undefined ? fgOf(v) : '#1d3557') },
      g.label));
    grp.appendChild(makeEl('text', { x:g.x, y:g.y+9, 'text-anchor':'middle',
      'dominant-baseline':'central',
      style:'font:600 10px ui-monospace,monospace; fill:#666',
      id:'gv-'+id }, v !== undefined ? String(v) : '?'));
    gateLayer.appendChild(grp);
  }

  // Wire G6 โ†’ output
  const outV = vals['G6'];
  wireLayer.appendChild(makeEl('path', {
    d: bezier(rightX('G6'), centerY('G6'), OUT_POS.x-22, OUT_POS.y),
    fill:'none', stroke: outV !== undefined ? colorOf(outV) : '#94a3b8',
    'stroke-width': outV !== undefined ? 2 : 1.6, id:'w-G6-out'
  }));

  // Output node
  const outGrp = makeEl('g', {});
  outGrp.appendChild(makeEl('rect', { x:OUT_POS.x-22, y:OUT_POS.y-18, width:44, height:36, rx:6,
    fill: outV !== undefined ? bgOf(outV) : '#f8fafc',
    stroke: outV !== undefined ? colorOf(outV) : '#475569', 'stroke-width':1.5 }));
  outGrp.appendChild(makeEl('text', { x:OUT_POS.x, y:OUT_POS.y-4, 'text-anchor':'middle',
    'dominant-baseline':'central',
    style:'font:700 11px ui-monospace,monospace; fill:'+(outV !== undefined ? fgOf(outV) : '#334155') }, 'OUT'));
  outGrp.appendChild(makeEl('text', { x:OUT_POS.x, y:OUT_POS.y+9, 'text-anchor':'middle',
    'dominant-baseline':'central',
    style:'font:600 11px ui-monospace,monospace; fill:#666', id:'out-val' },
    outV !== undefined ? String(outV) : '?'));
  gateLayer.appendChild(outGrp);

  // Level labels
  const lvlX = [130, 220, 310, 380];
  const lvlNames = ['Level 1', 'Level 2', 'Level 3', 'Level 4'];
  for (let i=0; i<lvlX.length; i++) {
    gateLayer.appendChild(makeEl('text', { x:lvlX[i], y:276, 'text-anchor':'middle',
      style:'font:500 9px system-ui,sans-serif; fill:#94a3b8' }, lvlNames[i]));
  }
}

// โ”€โ”€ Gate computation โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function computeGate(id) {
  const g = DEFS[id];
  const ins = g.ins.map(i => vals[i]);
  if (g.op === 'NOT') return ins[0] ? 0 : 1;
  if (g.op === 'AND') return (ins[0] && ins[1]) ? 1 : 0;
  if (g.op === 'OR')  return (ins[0] || ins[1]) ? 1 : 0;
}

// โ”€โ”€ Animation โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let animating = false;
function evaluate() {
  if (animating) return;
  animating = true;
  document.getElementById('evaluate').disabled = true;
  // Reset
  for (const k in vals) delete vals[k];
  Object.assign(vals, inputs);
  buildSVG();
  setStatus('Starting evaluationโ€ฆ', 'running');
  let lvlIdx = 0;

  function nextLevel() {
    if (lvlIdx >= LEVELS.length) {
      const out = vals['G6'];
      buildSVG();
      setStatus(
        fmt('Done โ€” Output = %out%   (A=%A%, B=%B% โ†’ A XOR B = %v%)', { out: out, A: inputs.A, B: inputs.B, v: inputs.A ^ inputs.B }), 'ok');
      animating = false;
      document.getElementById('evaluate').disabled = false;
      console.log(fmt('CVP: A=%A% B=%B% G1=%G1% G2=%G2% G3=%G3% G4=%G4% G5=%G5% G6=%G6% expected XOR=%v%', { A: inputs.A, B: inputs.B, G1: vals.G1, G2: vals.G2, G3: vals.G3, G4: vals.G4, G5: vals.G5, G6: vals.G6, v: inputs.A^inputs.B }));
      return;
    }
    const level = LEVELS[lvlIdx++];
    for (const id of level) vals[id] = computeGate(id);
    buildSVG();
    setStatus(fmt('Level %lvlIdx%: evaluated [%level%]', { lvlIdx: lvlIdx, level: level.join(', ') }), 'running');
    setTimeout(nextLevel, 700);
  }
  setTimeout(nextLevel, 400);
}

function setStatus(msg, cls) {
  const s = document.getElementById('status');
  s.textContent = msg; s.className = 'status ' + (cls||'');
}

document.getElementById('evaluate').addEventListener('click', evaluate);
document.getElementById('reset').addEventListener('click', () => {
  animating = false;
  document.getElementById('evaluate').disabled = false;
  for (const k in vals) delete vals[k];
  Object.assign(vals, inputs);
  buildSVG();
  setStatus('Click A or B to toggle, then press Evaluate.', '');
});

buildSVG();
Result
Console

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 nn gates arranged in a chain of depth nn, even infinitely many processors cannot finish in fewer than nn steps โ€” depth is the bottleneck, not breadth.

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

The Real Complexity

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

  • A problem LL is P-complete if LโˆˆPL \in \mathrm{P} and every problem in P reduces to LL 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 ฮ˜(n)\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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

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