Counting problem (complexity)

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 c_R is a search problem while #R is a decision problem, however c_R 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 c_R, is to make this binary search possible).

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.

External links

"counting problem". PlanetMath.
"counting complexity class". PlanetMath.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.