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).
随便看	LinearErasing linear erasing LinearExtension linear extension LinearFormulasForPythagoreanTriples linear formulas for Pythagorean triples LinearFunction linear function LinearFunctional linear functional LinearInvolution linear involution LinearIsomorphism linear isomorphism Linearization linearization LinearLanguage linear language LinearLeastSquares linear least squares LinearLeastSquaresFit linear least squares fit LinearlyDisjoint linearly disjoint LinearlyIndependent