counting problem

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

单词	CountingProblem
释义	counting problem If $R$ is a search problem then $c_{R}(x)=\|\\{y\\mid R(x)\\}\|$ is the corresponding counting function and $\\#R=\\{(x,y)\\mid y\\leq c_{R}(x)\\}$ denotes the corresponding counting problem. Note that $c_{R}$ is a search problem while $\\#R$ is a decision problem, however $c_{R}$ can be $\\mathcal{C}$ Cook reduced to $\\#R$ (for appropriate $\\mathcal{C}$ ) using a binary search (the reason $\\#R$ is defined the way it is, rather than being the graph of $c_{R}$ , is to make this binary search possible).
随便看	Prime prime PrimeConstant prime constant PrimeCountingFunction prime counting function PrimeDifferenceFunction prime difference function PrimeElement prime element PrimeElementIsIrreducibleInIntegralDomain prime element is irreducible in integral domain PrimeFactorizationsOfSomeSmallHighlyCompositeNumbers prime factorizations of some small highly composite numbers PrimeFactorsOfPythagoreanHypotenuses prime factors of Pythagorean hypotenuses PrimeFactorsOfXn1 prime factors of x^n-1 PrimefreeSequence primefree sequence PrimeGap prime gap PrimeHarmonicSeries prime harmonic series PrimeHarmonicSeriesDivergesChebyshevsProof