range problem

A range problem is a weakened form of a search problem. It consists of two functions $f_{l}$ and $f_{u}$ (the lower and upper bounds) and a linear ordering $<$ on the ranges of $f_{1}$ and $f_{2}$ . A Turing machine solves a range problem if, for any $x$ , the machine eventually halts with an output $y$ such that $f_{1}(x)<y<f_{2}(x)$ .

For example, given any function $f$ with range in $\\mathbb{R}$ and any $g:\\mathbb{N}\\rightarrow\\mathbb{R}$ , the strong range problem $\\operatorname{StrongRange}_{g}(f)$ is given by lower bound $f(x)\\cdot(1-\\frac{1}{1-g(|x|)})$ and upper bound $f(x)\\cdot(1-\\frac{1}{1+g(|x|)})$ (note that $g$ is passed the length of $x$ , not the value, which need not even be a number).

单词	RangeProblem
释义	range problem A range problem is a weakened form of a search problem. It consists of two functions $f_{l}$ and $f_{u}$ (the lower and upper bounds) and a linear ordering $<$ on the ranges of $f_{1}$ and $f_{2}$ . A Turing machine solves a range problem if, for any $x$ , the machine eventually halts with an output $y$ such that $f_{1}(x)<y<f_{2}(x)$ . For example, given any function $f$ with range in $\\mathbb{R}$ and any $g:\\mathbb{N}\\rightarrow\\mathbb{R}$ , the strong range problem $\\operatorname{StrongRange}_{g}(f)$ is given by lower bound $f(x)\\cdot(1-\\frac{1}{1-g(\|x\|)})$ and upper bound $f(x)\\cdot(1-\\frac{1}{1+g(\|x\|)})$ (note that $g$ is passed the length of $x$ , not the value, which need not even be a number).
随便看	discontinuous DiscontinuousAction discontinuous action Discrete discrete DiscreteCosineTransform discrete cosine transform DiscreteDensityFunction discrete density function DiscreteFourierTransform discrete Fourier transform DiscreteLogarithm discrete logarithm DiscreteSineTransform discrete sine transform DiscreteSpace discrete space DiscreteTimeFourierTransformInRelationWithContinuousTimeFourierTransform discrete time Fourier transform in relation with continuous time Fourier transform DiscreteValuation discrete valuation DiscreteValuationRing discrete valuation ring DiscreteWhiteNoise discrete white noise