Counting Problem (complexity)
Get Counting Problem Complexity essential facts below. View Videos or join the Counting Problem Complexity discussion. Add Counting Problem Complexity to your topic list for future reference or share this resource on social media.
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

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

If NX is a complexity class associated with non-deterministic machines then #X = {#R | RNX} is the set of counting problems associated with each search problem in NX. In particular, #P is the class of counting problems associated with NP search problems. Just as NP has NP-complete problems via many-one reductions, #P has complete problems via parsimonious reductions, problem transformations that preserve the number of solutions.

See also

External links

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

  This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.



Music Scenes