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 ,円}${\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)\}}${\displaystyle \#R=\{(x,y)\mid y\leq c_{R}(x)\}}

denotes the corresponding decision problem.

Note that c_R is a search problem while #R is a decision problem, however c_R 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 c_R, is to make this binary search possible).

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]

• GapP

• "counting problem". PlanetMath .
• "counting complexity class". PlanetMath .

• Computational problems
• Theoretical computer science stubs

• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from October 2014
• All articles needing additional references
• All stub articles