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

Title	range problem
Canonical name	RangeProblem
Date of creation	2013-03-22 13:02:25
Last modified on	2013-03-22 13:02:25
Owner	Henry (455)
Last modified by	Henry (455)
Numerical id	5
Author	Henry (455)
Entry type	Definition
Classification	msc 68Q25
Defines	strong range problem
Defines	strong range