# Counting problem (complexity)

Appearance

(Redirected from Counting complexity class)

This article needs additional citations for verification. (October 2014) |

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 *c _{R}* is a search problem while #

*R*is a decision problem, however

*c*can be

_{R}*Cook-reduced to #*

**C***R*(for appropriate

*) using a binary search (the reason #*

**C***R*is defined the way it is, rather than being the graph of

*c*, is to make this binary search possible).

_{R}## Counting complexity class[edit]

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.^{[1]}

## See also[edit]

## References[edit]

**^**Barak, Boaz (Spring 2006). "Complexity of counting" (PDF).*Princeton University*.

## External links[edit]