Counting Problem (complexity)
Get Counting Problem Complexity essential facts below. View Videos or join the Counting Problem Complexity discussion. Add Counting Problem Complexity to your PopFlock.com topic list for future reference or share this resource on social media.
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

${\displaystyle c_{R}(x)=\vert \{y\mid R(x,y)\}\vert \,}$

is the corresponding counting function and

${\displaystyle \#R=\{(x,y)\mid y\leq c_{R}(x)\}}$

denotes the corresponding decision problem.

Note that cR is a search problem while #R is a decision problem, however cR can be C Cook-reduced to #R (for appropriate C) using a binary search (the reason #R is defined the way it is, rather than being the graph of cR, is to make this binary search possible).

## Counting complexity class

If NX is a complexity class associated with non-deterministic machines then #X = {#R | RNX} 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.