title: Counting problem (complexity)
text: # 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 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
  
  If NX is a complexity class associated with non-deterministic machines then #X = {#R | R ∈ NX} 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.
  
  