Counting problem Definition and 58 Threads

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
)
=
|
{
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 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).

View More On Wikipedia.org