6
$\begingroup$

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:

$\endgroup$
4
$\begingroup$

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.

This is a well-studied problem, where the key notion is the teaching dimension (which is the minimum size of a teaching set), see here: https://www.cs.umd.edu/sites/default/files/scholarly_papers/NealGupta.pdf

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).

As you can see from the discussion in that paper I linked, the teaching dimension is a rather stringent notion, which motivates more "interesting" variants, such as the recursive teaching dimension. Here again, I encourage you to explore its natural real-valued extensions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.