Counting problem (complexity)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

c_R(x)=\vert\{y\mid R(x,y)\}\vert \,

is the corresponding counting function and

\#R=\{(x,y)\mid y\leq c_R(x)\}

denotes the corresponding counting 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]

If NC is a complexity class associated with non-deterministic machines then #C = {#R | RNC} is the set of counting problems associated with each search problem in NC. In particular, #P is the class of counting problems associated with NP search problems.

External links[edit]