# 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 $$.

For example, given any function $f$ with range in $\mathbb{R}$ and any $g:\mathbb{N}\to \mathbb{R}$, the *strong range problem* ${\mathrm{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 |