Counting problem (computability theory)

From Wikipedia, the free encyclopedia

In 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).

[edit] Counting complexity class

If NC is a complexity class associated with non-deterministic machines then #C = {#R | R ∈ NC} 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.

This article incorporates material from counting problem on PlanetMath, which is licensed under the GFDL.
This article incorporates material from counting complexity class on PlanetMath, which is licensed under the GFDL.