Counting problem (complexity)

In computability theory, if R is a search problem then

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

is the corresponding counting function and

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

denotes the corresponding counting 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).

counting problem at PlanetMath.