This article needs additional citations for verification. (October 2014) (Learn how and when to remove this template message) |

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

If *NX* is a complexity class associated with non-deterministic machines then *#X* = {*#R* | *R* ∈ *NX*} is the set of counting problems associated with each search problem in *NX*. In particular, **#P** is the class of counting problems associated with **NP** search problems.
Just as NP has NP-complete problems via many-one reductions, #P has complete problems via parsimonious reductions, problem transformations that preserve the number of solutions.

## See also

## External links

P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |