Counting problem (complexity)


In computational complexity theory and computability theory, a counting problem is a type of computational problem. If R is a search problem then
is the corresponding counting function and
denotes the corresponding decision problem.
Note that cR is a function problem while #R is a decision problem, however cR can be C Cook-reduced to #R using a binary search.

Counting complexity class

Just as NP has NP-complete problems via many-one reductions, #P has #P-complete problems via parsimonious reductions, problem transformations that preserve the number of solutions.