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 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
P ≟ NP | This theoretical computer science–related article is a stub. You can help Infogalactic by expanding it. |