Consider the following computational problem, where $I$ is the real interval $[-1,1]$:
There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of the kind: "Given $x\in I$, what is $f(x)$?". Let $x_0$ be an element of $I$ such that $f(x_0)=0$ (if it exists). Your goal is to find a value $x$ such that $|x-x_0|<\epsilon$. How many queries do you need, as a function of $\epsilon$?
All real numbers have infinite precision, as in the Real RAM model. It is allowed to do arbitrary computaitons on such real numbers - the only costly operations are the queries.
Here, the solution is simple: using binary search, the interval in which $x$ can lie shrinks by 2 after each query, so $\log_2(1/\epsilon)$ queries are sufficient. This is also an upper bound, since an adversary can always answer in such a way that the possible interval for $x$ shrinks by at most 2 after each query.
However, one can think of more complicated problems of this kind, with several different functions and possibly different kinds of queries.
What is a term, and some references, for this kind of computational problems?
Related posts in other sites: