Short description: Type of computational problem

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

[math]\displaystyle{ c_R(x)=\vert\\{y\mid R(x,y)\\}\vert \, }[/math]

is the corresponding counting function and

[math]\displaystyle{ \\#R=\\{(x,y)\mid y\leq c_R(x)\\} }[/math]

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

If NX is a complexity class associated with non-deterministic machines then #X = {#R | R ∈ NX} is the set of counting problems associated with each search problem in NX. In particular, #P is the class of counting problems associated with NP search problems. Just as NP has NP-complete problems via many-one reductions, #P has complete problems via parsimonious reductions, problem transformations that preserve the number of solutions.

## See also

* GapP

## External links

* "counting problem". http://planetmath.org/?op=getobj&from=objects&id=3439.
* "counting complexity class". http://planetmath.org/?op=getobj&from=objects&id=3444.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Counting problem (complexity). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Counting_problem_(complexity)&oldid=74717"