= Counting complexity
{wiki}
<Counting complexity> studies the computational resources needed to count solutions. For a <polynomial time> decidable <binary relation> $R$ and a <polynomial> $p$, a standard counting <function> is
$$
f(x)=\left|\{y\in\{0,1\}^{p(|x|)}:R(x,y)\}\right|.
$$
The <complexity class> $\#\mathbf P$ consists of these <functions>, equivalently the numbers of accepting computations of <Nondeterministic Turing machines> running in <polynomial time>. The witness encoding matters: counting computation paths and counting distinct outputs can give different answers.
For the <propositional formula> $x\lor y$, the satisfying <Boolean valuations> are $01$, $10$ and $11$, so the answer is three. The associated <decision problem> asks only whether that count is positive. For a zero-one <matrix>, the <permanent of a matrix> counts <perfect matchings> in a <bipartite graph>. Testing whether any such <perfect matching> exists admits a <polynomial-time algorithm>, while counting them is $\#\mathbf P$-complete under <polynomial-time Turing reductions>.<The Complexity of Computing the Permanent by Leslie G. Valiant>[sections 1–2 and Theorem 1]{ref}
Back to article page
