Editing Counting problem (complexity)

{{short description|Type of computational problem}}
{{More citations needed|date=October 2014}}
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 decision 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 reduction|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==
{{see also| ♯P | label1=#P | ♯P-complete | label2=#P-complete}}

Just as NP has [[NP-complete]] problems via [[many-one reduction]]s, #P has #P-complete problems via [[parsimonious reduction]]s, problem transformations that preserve the number of solutions.<ref>{{cite web |last1=Barak |first1=Boaz |title=Complexity of counting |url=https://www.cs.princeton.edu/courses/archive/spring06/cos522/count.pdf |website=Princeton University |date=Spring 2006}}</ref>

== See also == 
* [[GapP]]

==References==
{{refs}}

==External links==
* {{PlanetMath reference|urlname=CountingProblem|title=counting problem}}
* {{PlanetMath reference|urlname=CountingComplexityClass|title=counting complexity class}}

[[Category:Computational problems]]


{{Comp-sci-theory-stub}}