Counting problem (complexity)

Template:Short description Template:More citations needed In computational complexity theory and computability theory, a counting problem is a type of computational problem. If R is a search problem then

<math>c_R(x)=\vert\{y\mid R(x,y)\}\vert \,</math>

is the corresponding counting function and

<math>\#R=\{(x,y)\mid y\leq c_R(x)\}</math>

denotes the corresponding decision 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

Just as NP has NP-complete problems via many-one reductions, #P has #P-complete problems via parsimonious reductions, problem transformations that preserve the number of solutions.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

See also

• GapP

External links

• {{#invoke:citation/CS1|citation

|CitationClass=web }}

• {{#invoke:citation/CS1|citation

|CitationClass=web }}

Template:Comp-sci-theory-stub