PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
create new user
forget your password?
Main Menu
range problem (Definition)

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(\vert x\vert)})$ and upper bound $ f(x)\cdot(1-\frac{1}{1+g(\vert x\vert)})$ (note that $ g$ is passed the length of $ x$, not the value, which need not even be a number).

"range problem" is owned by Henry.
(view preamble)

View style:

Also defines:  strong range problem, strong range

Cross-references: even, length, lower bound, eventually, Turing machine, ranges, linear ordering, upper bounds, functions, search problem

This is version 2 of range problem, born on 2002-09-07, modified 2005-02-14.
Object id is 3442, canonical name is RangeProblem.
Accessed 2329 times total.

AMS MSC68Q25 (Computer science :: Theory of computing :: Analysis of algorithms and problem complexity)

Pending Errata and Addenda
[ View all 1 ]
Style: Expand: Order:
forum policy

No messages.

rate | post | correct | update request | add derivation | add example | add (any)