Counting problem (complexity)

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> and <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a>, a counting problem is a type of <a href="/facts/Computational_problem/jQ7bYUVh">computational problem</a>. If R is a <a href="/facts/Search_problem/eWnSpkAR">search problem</a> then

c
          
            R
          
        
        (
        x
        )
        =
        |
        {
        y
        ∣
        R
        (
        x
        ,
        y
        )
        }
        |
        
      
    
    {\displaystyle c_{R}(x)=\vert \{y\mid R(x,y)\}\vert \,}

is the corresponding counting function and

#
        R
        =
        {
        (
        x
        ,
        y
        )
        ∣
        y
        ≤
        
          c
          
            R
          
        
        (
        x
        )
        }
      
    
    {\displaystyle \#R=\{(x,y)\mid y\leq c_{R}(x)\}}

denotes the corresponding decision problem. 
Note that cR is a search problem while #R is a decision problem, however cR can be C <a href="/facts/Cook_reduction/qczcQTbz">Cook-reduced</a> to #R (for appropriate C) using a <a href="/facts/Binary_search/FFmQzunc">binary search</a> (the reason #R is defined the way it is, rather than being the graph of cR, is to make this binary search possible).

Counting problem (complexity) open-in-new

Counting problem (complexity)