Counting problem (complexity)

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Counting problem" complexity – news · newspapers · books · scholar · JSTOR (October 2014) (Learn how and when to remove this message)

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 c_R is a search problem while #R is a decision problem, however c_R can be C

(the reason #R is defined the way it is, rather than being the graph of c_R, is to make this binary search possible).

Counting complexity class

If NX is a complexity class associated with

search problems. Just as NP has , problem transformations that preserve the number of solutions.

See also

• GapP

External links

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