counting problem

If R is a search problem then cR(x)=|{yR(x)}| is the corresponding counting function and #R={(x,y)ycR(x)} denotes the corresponding counting problem. Note that cR is a search problem while #R is a decision problemMathworldPlanetmath, however cR can be 𝒞 Cook reduced to #R (for appropriate 𝒞) using a binary searchMathworldPlanetmath (the reason #R is defined the way it is, rather than being the graph of cR, 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