counting problem

If $R$ is a search problem then $c_{R}(x)=|\{y\mid R(x)\}|$ 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 $\mathcal{C}$ Cook reduced to $\#R$ (for appropriate $\mathcal{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).

Title	counting problem
Canonical name	CountingProblem
Date of creation	2013-03-22 13:02:17
Last modified on	2013-03-22 13:02:17
Owner	Henry (455)
Last modified by	Henry (455)
Numerical id	6
Author	Henry (455)
Entry type	Definition
Classification	msc 68Q25