Introduction

We usually measure computation by time — how many steps an algorithm takes. Circuit complexity uses a different ruler. It asks: if you had to build a function purely out of logic gates — AND, OR and NOT wired together — how many gates would you need, and how deep would the chain be?

Every Boolean function can be built this way. A circuit has size (the total number of gates) and depth (the length of the longest path from an input to the output). Size is roughly "how much hardware"; depth is roughly "how many sequential steps" — how parallel the computation can be.

These two numbers fight each other. The same function can often be built deep and narrow (few gates per layer, many layers) or shallow and wide (many gates working in parallel, fewer layers). Understanding exactly how big a circuit has to be — its lower bound — turns out to be one of the deepest open questions in all of computer science.

Build a Circuit

Below is the same function — the XOR of four input bits (output 1 when an odd number of inputs are 1) — built two ways from AND, OR and NOT gates. Flip the input switches and watch both circuits compute the identical answer.

<p class="hint">The same function — <b>XOR of four bits</b> (output 1 when an odd number of inputs are 1) — built two ways from AND, OR and NOT gates. Flip the switches; both circuits agree. Then toggle the layout and watch <b>depth</b> trade against <b>width</b>.</p>
<div class="inputs" id="inputs"></div>
<div class="layout-btns">
  <button id="balanced" type="button">Balanced (shallow)</button>
  <button id="chained" type="button" class="ghost">Chained (deep)</button>
</div>
<div id="diagram" class="diagram"></div>
<div class="readout">
  <div class="metric"><span class="k">Output</span><span class="v" id="out">0</span></div>
  <div class="metric"><span class="k">Gates (size)</span><span class="v" id="size">0</span></div>
  <div class="metric"><span class="k">Depth</span><span class="v" id="depth">0</span></div>
</div>
<div class="status" id="status"></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; }
.inputs { display: flex; gap: .6rem; flex-wrap: wrap; margin: .3rem 0 .6rem; }
.bit { display: flex; flex-direction: column; align-items: center; gap: .25rem; }
.bit button { width: 44px; height: 44px; font: 700 18px ui-monospace, monospace;
              border-radius: 8px; border: 1px solid #adb1b8; background: #e8eef3;
              color: #1d3557; cursor: pointer; }
.bit button.on { background: #1d3557; color: #fff; border-color: #1d3557; }
.bit .lbl { font: 600 12px system-ui; color: #555; }
.layout-btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
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; }
.diagram { display: flex; flex-direction: column; gap: 10px; margin: .4rem 0;
           padding: .6rem; background: #f5f7fa; border-radius: 10px; min-height: 90px; }
.layer { display: flex; gap: 8px; flex-wrap: wrap; justify-content: center; }
.gate { padding: .35rem .55rem; border-radius: 8px; font: 700 13px ui-monospace, monospace;
        border: 1px solid #cdd9e3; background: #fff; min-width: 60px; text-align: center; }
.gate.hot { background: #d5f0dd; border-color: #5bbd7a; }
.gate small { display: block; font: 500 10px system-ui; color: #777; }
.readout { display: flex; gap: 1.4rem; flex-wrap: wrap; margin: .6rem 0; }
.metric { display: flex; flex-direction: column; }
.metric .k { font: 600 11px system-ui; color: #777; text-transform: uppercase; letter-spacing: .04em; }
.metric .v { font: 800 22px ui-monospace, monospace; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.3em; color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Circuit complexity: the same Boolean function, two circuits.
// XOR of 4 bits = parity. Built only from AND / OR / NOT.
//   xor2(a,b) = (a OR b) AND NOT(a AND b)
// Each xor2 costs 4 gates (OR, AND, NOT, AND) and has depth 3.
//   Balanced: xor2(xor2(a,b), xor2(c,d))  -> 3 xor2 blocks, two run in parallel
//   Chained:  xor2(xor2(xor2(a,b),c),d)   -> 3 xor2 blocks strung in a line
const AND=(x,y)=>x&y, OR=(x,y)=>x|y, NOT=x=>x^1;
function xor2(a,b){ const or=OR(a,b), and=AND(a,b), nand=NOT(and); return AND(or,nand); }

const bits=[0,0,0,0];
let mode='balanced';

// Build a layered description of the chosen circuit for both display and metrics.
function build(){
  const [a,b,c,d]=bits;
  if(mode==='balanced'){
    const p=xor2(a,b), q=xor2(c,d), out=xor2(p,q);
    // 3 xor2 blocks; the two leaf blocks share layers -> depth 3+3 = 6, width up to 2 blocks wide.
    return {
      out,
      layers:[
        [g('OR',OR(a,b)),g('OR',OR(c,d))],
        [g('AND',AND(a,b)),g('AND',AND(c,d))],
        [g('NOT',NOT(AND(a,b))),g('NOT',NOT(AND(c,d)))],
        [g('AND a⊕b',p),g('AND c⊕d',q)],
        [g('OR',OR(p,q))],
        [g('AND',AND(p,q))],
        [g('NOT',NOT(AND(p,q)))],
        [g('AND out',out)]
      ]
    };
  } else {
    const p=xor2(a,b), q=xor2(p,c), out=xor2(q,d);
    return {
      out,
      layers:[
        [g('OR',OR(a,b))],[g('AND',AND(a,b))],[g('NOT',NOT(AND(a,b)))],[g('AND a⊕b',p)],
        [g('OR',OR(p,c))],[g('AND',AND(p,c))],[g('NOT',NOT(AND(p,c)))],[g('AND ⊕c',q)],
        [g('OR',OR(q,d))],[g('AND',AND(q,d))],[g('NOT',NOT(AND(q,d)))],[g('AND out',out)]
      ]
    };
  }
}
function g(label,val){ return {label,val}; }

function refInputs(){
  const wrap=document.getElementById('inputs'); wrap.innerHTML='';
  ['a','b','c','d'].forEach((name,i)=>{
    const div=document.createElement('div'); div.className='bit';
    const btn=document.createElement('button'); btn.textContent=bits[i];
    if(bits[i]) btn.classList.add('on');
    btn.addEventListener('click',()=>{ bits[i]^=1; render(); });
    const lbl=document.createElement('span'); lbl.className='lbl'; lbl.textContent=name;
    div.appendChild(btn); div.appendChild(lbl); wrap.appendChild(div);
  });
}
function render(){
  refInputs();
  const c=build();
  const dia=document.getElementById('diagram'); dia.innerHTML='';
  c.layers.forEach(layer=>{
    const row=document.createElement('div'); row.className='layer';
    layer.forEach(gt=>{
      const el=document.createElement('div'); el.className='gate'+(gt.val?' hot':'');
      el.innerHTML=gt.label+'<small>'+gt.val+'</small>';
      row.appendChild(el);
    });
    dia.appendChild(row);
  });
  const size=c.layers.reduce((s,l)=>s+l.length,0);
  const depth=c.layers.length;
  document.getElementById('out').textContent=c.out;
  document.getElementById('size').textContent=size;
  document.getElementById('depth').textContent=depth;
  const expected=bits.reduce((x,y)=>x^y,0);
  const ok=(c.out===expected);
  const s=document.getElementById('status');
  s.textContent=ok ? (fmt('✓ Both layouts compute the same XOR = %expected%  (%v%)', { expected: expected, v: mode==='balanced'?'shallow & wide':'deep & narrow' })) : '✗ mismatch';
  s.style.color=ok?'#0a7d33':'#c92f3c';
}
document.getElementById('balanced').addEventListener('click',()=>{ mode='balanced'; render(); });
document.getElementById('chained').addEventListener('click',()=>{ mode='chained'; render(); });
render();
Result
Console

Press Balanced (shallow) and the gates fan out into a wide, parallel tree: more gates per layer, but only a few layers deep. Press Chained (deep) and the same logic is strung into a long thin sequence: fewer gates side by side, but a much longer path from input to output. Same function, same answer — yet the depth and width trade places. That trade-off is the whole game of circuit complexity.

The Real Complexity

Here is the strange part. In 1949 Claude Shannon proved by counting that almost every Boolean function on n bits needs an exponentially large circuit — roughly 2n2^{n}⁄n gates. Most functions are monstrously expensive.

  • Status: open. Despite that, for any specific, explicitly described function, the best lower bound anyone has proven is only about 5n gates (Iwama–Lachish–Morizumi–Raz and successors). We know the hard functions are out there but we cannot point at one and prove it.
  • Why it matters for P vs NP. If someone proved that a function in NP — say SAT — requires super-polynomial circuits, that would imply P ≠ NP. Circuit lower bounds are one of the leading attacks on the million-dollar question.
  • The barrier. In 1994 Razborov and Rudich showed that most known techniques are "natural proofs" — and natural proofs strong enough to settle P vs NP would, paradoxically, break the very cryptography we believe is secure. So the obvious roads are blocked.
  • Depth vs size. Restricting depth (constant-depth circuits, the class AC0AC^{0}) does let us prove exponential lower bounds — Furst–Saxe–Sipser and Håstad showed parity needs huge shallow circuits. Lifting that to general circuits is the open frontier.

So circuit complexity sits in a tantalizing place: we can prove hard functions are everywhere, but we cannot finger a single explicit one — and doing so would crack P vs NP wide open.

Where It Matters

Counting gates is not just theory — the size-versus-depth trade-off shapes real systems:

  • Chip design. Every processor is a circuit. Fewer gates means less silicon and power; shallower depth means a shorter critical path and a faster clock. Designers literally trade width for depth.
  • Parallel computing. Depth measures how parallel a computation can be: a shallow circuit finishes in few sequential rounds. The class NC of efficiently-parallelizable problems is defined by shallow, polynomial-size circuits.
  • Cryptography. The "natural proofs" barrier links hard-to-build functions to secure pseudorandom generators — the reason we can't easily prove lower bounds is the same reason cryptography can exist.
  • Defining efficiency. Polynomial-size circuits (the class P/poly) are a clean, hardware-flavored stand-in for "feasible," used throughout complexity theory alongside SAT and the rest of the NP world.

Master gates and depth and you have met the hardware-level view of computation — the same view that turns abstract questions about algorithms into concrete questions about wires.

Conclusion

Circuit complexity swaps the clock for a pile of gates and asks the most physical question imaginable: how much hardware does this function demand? Shannon told us the answer is usually "an astronomical amount" — and yet, three-quarters of a century later, we still cannot point at one explicit function and prove it.

That gap is not a footnote. It is the locked door in front of P vs NP: pry open a strong enough circuit lower bound and the biggest question in computer science falls with it. For now, the gates keep their secret — we know the giants are out there, hidden among the functions, and we simply cannot name one.

Share this article

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

Comments

Loading comments...

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