Counting Problem

complexity-theory computation

Definition

Counting Problem

A counting problem is a computational problem that asks for the number of solutions to a given search problem, rather than merely determining the existence of a solution. Formally, it is defined by a function $f:\{0,1{\}}^{\ast }\to \mathbb{N}$ such that for an input $x$, $f(x)=|\{y\mid (x,y)\in R\}|$, where $R$ is a polynomial-time decidable binary relation.