A range problem is a weakened form of a search problem. It consists of two functions and (the lower and upper bounds) and a linear ordering on the ranges of and . A Turing machine solves a range problem if, for any , the machine eventually halts with an output such that .
For example, given any function with range in and any , the strong range problem is given by lower bound and upper bound (note that is passed the length of , not the value, which need not even be a number).
|Date of creation||2013-03-22 13:02:25|
|Last modified on||2013-03-22 13:02:25|
|Last modified by||Henry (455)|
|Defines||strong range problem|