View source for MGH

In [[computational complexity theory]] and [[computability theory]], a '''counting problem''' is a type of [[computational problem]]. If ''R'' is a [[search problem]] then 

:<math>c_R(x)=\vert\{y\mid R(x,y)\}\vert \,</math>

is the corresponding [[counting function]] and

:<math>\#R=\{(x,y)\mid y\leq c_R(x)\}</math>

denotes the corresponding counting problem. 

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

==Counting complexity class==
If ''NC'' is a complexity class associated with [[nondeterministic algorithm|non-deterministic]] machines then ''#C'' = {''#R'' | ''R'' &isin; ''NC''} is the set of counting problems associated with each [[search problem]] in ''NC''. In particular, '''[[Sharp-P|#P]]''' is the class of counting problems associated with '''[[NP (complexity)|NP]]''' search problems.

==External links==
* {{PlanetMath reference|id=3439|title=counting problem}}
* {{PlanetMath reference|id=3444|title=counting complexity class}}

{{Comp-sci-theory-stub}}

[[Category:Computational problems]]