Counting complexity studies the computational resources needed to count solutions. For a polynomial time decidable binary relation and a polynomial , a standard counting function isThe complexity class 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 , the satisfying Boolean valuations are , and , 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 -complete under polynomial-time Turing reductions.[ref]
New to topics? Read the docs here!