Jump to content

Counting problem (complexity)

From Wikipedia, the free encyclopedia

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

[edit]

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.[1]

See also

[edit]

References

[edit]
  1. ^ Barak, Boaz (Spring 2006). "Complexity of counting" (PDF). Princeton University.
[edit]