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

is the corresponding counting function and

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

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