Introduction

Suppose I hand you a logic puzzle and ask: is there a way to make it true? Often that's easy — you find one assignment that works, show it to me, done. But now I change one word and ask: how many ways are there?

Suddenly the trick of "just show me one" is useless. To answer how many, you seemingly have to account for every possibility, even the ones you'd happily ignore when you only needed a single witness.

That gap between "does one exist?" (a yes/no decision) and "how many exist?" (a count) is not a detail. It marks the border of a whole complexity class called #P (pronounced "sharp-P"), and it is one of the cleanest examples of a problem where checking, deciding, and counting are three very different jobs.

Try It: Find One vs. Count Them All

Below is a small Boolean formula over a handful of variables. Two buttons, two very different jobs. Find one stops the instant it sees a single assignment that makes the formula true. Count all must keep going until it has examined the entire space of 2n2^{n} assignments.

<p class="hint">A Boolean formula over <b id="nlab">5</b> variables. Two jobs:
<b>Find one</b> assignment that makes it true (stops at the first hit), or
<b>Count all</b> assignments that make it true (must scan every row of the
2<sup>n</sup> truth table). Checking one row is instant — counting them all is the wall.</p>
<pre class="formula" id="formula"></pre>
<label class="slider">Variables (n): <input id="n" type="range" min="3" max="20" value="5">
  <span id="nval">5</span> &rarr; <b id="rows">32</b> rows</label>
<div class="btns">
  <button id="findone" type="button">Find one</button>
  <button id="countall" type="button">Count all</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status">Pick an action above.</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; }
.formula { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3;
           border-radius: 8px; padding: .6rem .8rem; margin: .3rem 0 .7rem;
           font: 600 14px ui-monospace, monospace; white-space: pre-wrap; }
.slider { display: block; font-size: .9rem; color: #444; margin: .2rem 0 .8rem; }
.slider input { vertical-align: middle; }
.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; }
.status { font-size: 1rem; font-weight: 600; margin: .7rem 0 0; min-height: 1.4em; line-height: 1.4; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status small { display: block; font-weight: 400; color: #555; margin-top: .2rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// #SAT vs SAT. Same formula, two questions:
//   "Find one"  -> stop at the first satisfying assignment (decision, NP-style).
//   "Count all" -> tally EVERY satisfying assignment (this is #P; #SAT is #P-complete, Valiant 1979). Both share a trivial per-row check; counting must walk all 2^n rows, so it explodes as n grows.
let n = 5;

// A fixed formula on the first variables, padded so it stays satisfiable for any n.
// Clauses are arrays of literals; a literal {v, neg} means x_v (or NOT x_v).
// Formula: (x0 OR x1) AND (NOT x1 OR x2) AND (x2 OR NOT x3 OR x4)
const CLAUSES = [
  [{v:0,neg:false},{v:1,neg:false}],
  [{v:1,neg:true },{v:2,neg:false}],
  [{v:2,neg:false},{v:3,neg:true },{v:4,neg:false}],
];

function litStr(l){ return (l.neg?'¬':'') + 'x' + l.v; }
function formulaStr(){
  return CLAUSES.map(c => '(' + c.map(litStr).join(' ∨ ') + ')').join('  ∧\n');
}

// Evaluate the formula for an assignment given as an integer bitmask (bit i = x_i).
function sat(mask){
  for(const clause of CLAUSES){
    let ok = false;
    for(const l of clause){
      const bit = (mask >> l.v) & 1;       // value of x_v
      const val = l.neg ? (bit === 0) : (bit === 1);
      if(val){ ok = true; break; }
    }
    if(!ok) return false;                   // a clause failed -> formula false
  }
  return true;
}
function bits(mask){ let s=''; for(let i=0;i<n;i++) s += (mask>>i)&1; return s; }

// Find one: scan until the first satisfying assignment, then stop.
function findOne(){
  const total = 2**n;
  for(let mask=0; mask<total; mask++){
    if(sat(mask)) return { found:true, at:mask, scanned:mask+1, total };
  }
  return { found:false, scanned:total, total };
}
// Count all: never short-circuits; tallies every satisfying row.
function countAll(){
  const total = 2**n; let count=0;
  for(let mask=0; mask<total; mask++){ if(sat(mask)) count++; }
  return { count, total };
}

function setStatus(html, cls){ const s=document.getElementById('status'); s.innerHTML=html; s.className='status '+(cls||''); }
function refresh(){
  document.getElementById('formula').textContent = formulaStr();
  document.getElementById('nlab').textContent = n;
  document.getElementById('nval').textContent = n;
  document.getElementById('rows').textContent = (2**n).toLocaleString('en-US');
}

document.getElementById('n').addEventListener('input', e => {
  n = parseInt(e.target.value,10); refresh(); setStatus('Pick an action above.','');
});
document.getElementById('findone').addEventListener('click', () => {
  const r = findOne();
  if(r.found) setStatus(fmt('✓ Found one solution: x = %bits%<small>Stopped after scanning %scanned% of %total% rows — finding one can quit early.</small>', { bits: bits(r.at), scanned: r.scanned, total: r.total.toLocaleString('en-US') }),'ok');
  else setStatus('No satisfying assignment exists.','bad');
});
document.getElementById('countall').addEventListener('click', () => {
  const r = countAll();
  setStatus(fmt('Σ Exactly %count% satisfying assignments<small>Had to examine ALL %total% rows of the truth table. This is #SAT — the #P-complete counting version.</small>', { count: r.count.toLocaleString('en-US'), total: r.total.toLocaleString('en-US') }),'ok');
  console.log('countAll result', 'n='+n, fmt('solutions=%count%', { count: r.count }), fmt('of %total%', { total: r.total }));
});
document.getElementById('reset').addEventListener('click', () => {
  n = 5; document.getElementById('n').value = 5; refresh(); setStatus('Pick an action above.','');
});
refresh();
Result
Console

Watch what happens as you add variables with the slider. Finding one solution usually returns almost immediately. Counting them all means walking the full truth table — and that table doubles in size with every variable you add. Five variables is 32 rows; twenty variables is over a million; sixty is more rows than there are atoms in your body. Checking any single row is trivial; tallying them all is the wall.

The Real Complexity

Here is the precise picture.

  • Checking one assignment is trivial: plug in the values, evaluate the formula, done in linear time.
  • Deciding existence ("is there at least one solution?") is the famous SAT problem — NP-complete, already believed hard.
  • Counting ("how many solutions?") is #SAT, and it defines the class #P. In 1979, Leslie Valiant introduced #P and proved that computing the permanent of a 0/1 matrix — a formula that looks almost identical to the easy-to-compute determinant — is #P-complete. Counting perfect matchings in a graph is the same problem.
  • #P sits above NP. With a single call to a #P oracle you can solve any NP problem (a count is positive exactly when a solution exists), and Toda's theorem (1991) shows the entire polynomial hierarchy reduces to #P. So #P is, in a strong sense, at least as hard as NP and almost certainly harder.

The punchline: even when finding one witness is easy, counting the witnesses can be #P-complete. The classic example is counting perfect matchings — deciding whether one exists is solvable in polynomial time, yet counting them is #P-complete. "How many?" is its own kind of hard, captured by the same engine behind P vs NP.

Where It Matters

"How many?" and its cousin "with what probability?" are everywhere, and almost all of them inherit #P's hardness:

  • Probabilistic inference: computing the probability of an event in a Bayesian network is #P-hard — exact reasoning over uncertainty is a counting problem. See Bayesian inference.
  • Statistical physics: the partition function that governs magnets and phase transitions is a giant weighted count, #P-hard in general.
  • Network reliability: "what's the chance this network stays connected if links fail at random?" is a #P-complete count.
  • Machine learning: normalizing many probabilistic models requires summing over exponentially many configurations — the same wall.

Because exact counting is so often #P-hard, the practical art is approximate counting and sampling (Monte Carlo methods, randomized algorithms), which trade an exact tally for a provably good estimate.

Conclusion

Counting changes everything. The same puzzle that surrenders a single answer in a blink can refuse to reveal how many answers it holds without marching through an exponential space. That is the lesson of #P: deciding, checking, and counting are genuinely different tasks, and the counting version can be the hardest of the three — even sitting above the whole NP world.

So the next time a question slides from "is there one?" to "how many?", respect the shift. You may have just crossed from a problem you can solve before lunch into one that, like P vs NP, the world's best algorithms still cannot crack — and our best hope is a clever estimate rather than an exact count.

Share this article

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

Comments

Loading comments...

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