Counting problem (complexity)#Counting complexity class
{{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
:
is the corresponding counting function and
:
denotes the corresponding decision problem.
Note that cR is a search problem while #R is a decision problem, however cR 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 cR, 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 reductions, #P has #P-complete problems via parsimonious reductions, problem transformations that preserve the number of solutions.{{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}}
== See also ==
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}}