# 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 CountingProblem 2013-03-22 13:02:17 2013-03-22 13:02:17 Henry (455) Henry (455) 6 Henry (455) Definition msc 68Q25