# counting problem

If $R$ is a search problem then ${c}_{R}(x)=|\{y\mid R(x)\}|$ is the corresponding counting function and $\mathrm{\#}R=\{(x,y)\mid y\le {c}_{R}(x)\}$ denotes the corresponding *counting problem*. Note that ${c}_{R}$ is a search problem while $\mathrm{\#}R$ is a decision problem^{}, however ${c}_{R}$ can be $\mathcal{C}$ Cook reduced to $\mathrm{\#}R$ (for appropriate $\mathcal{C}$) using a binary search^{} (the reason $\mathrm{\#}R$ is defined the way it is, rather than being the graph of ${c}_{R}$, is to make this binary search possible).

Title | counting problem |
---|---|

Canonical name | CountingProblem |

Date of creation | 2013-03-22 13:02:17 |

Last modified on | 2013-03-22 13:02:17 |

Owner | Henry (455) |

Last modified by | Henry (455) |

Numerical id | 6 |

Author | Henry (455) |

Entry type | Definition |

Classification | msc 68Q25 |