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).

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).

Title range problem RangeProblem 2013-03-22 13:02:25 2013-03-22 13:02:25 Henry (455) Henry (455) 5 Henry (455) Definition msc 68Q25 strong range problem strong range