# Complexity of approximating a real function using queries

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:

Not a complete answer, but hopefully a good starting point. It is very instructive to (always!) first consider the discrete analog of your question. If $$X$$ is some set and $$f:X\to\{0,1\}$$, what is the minimal number of evaluation queries needed to uniquely identify $$f$$? As already noted in the OP, the question only makes sense if one fixes a function class $$F$$ of possible candidate functions $$f$$ to consider.
A teaching set $$S\subset X$$ is such that the values of $$f$$ on $$S$$ uniquely identify $$f\in F$$, for a given fixed function class $$F$$.
Nothing is stopping you from defining an $$\epsilon$$-teaching dimension for real-valued functions. You can define an $$\epsilon$$-teaching set $$S\subset X$$ to be such that all $$f\in F$$ that agree on $$S$$ all lie within an $$\epsilon$$-tube (i.e., are all within $$\epsilon$$ in $$\ell_\infty$$ distance).