2
$\begingroup$

I am looking for information on problems of the following kind.

There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You have to find the unique $x\in[0,1]$ such that $f(x)=0$. You can access $f$ only through queries of the type "what is $f(x)$?". Besides asking queries, you are allowed to make arbitrary computations on real numbers for free. How many such queries do you need in order to approximate $x$ up to some constant $\epsilon$?

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?

EDIT: This MathOverflow post is related, but there it is required to use a finite number of registers with a finite precision; here it is allowed to make arbitrary computations in infinite precision real numbers for free (the only limitation is the number of queries).

$\endgroup$
5
  • $\begingroup$ Erel, I would rather post this question in cstheory.stackexchange.com. It looks a research problem. $\endgroup$ – user777 Jul 9 '20 at 1:27
  • $\begingroup$ There are several different models of real computation, specifying how the function $f$ is given to you and how you are allowed to manipulate real numbers. $\endgroup$ – Yuval Filmus Jul 9 '20 at 8:08
  • $\begingroup$ @YuvalFilmus I am interested in the model in which $f$ is given only through queries, and besides queries I am allowed to make arbitrary computations on infinite precision real numbers for free (the complexity is measured only by the number of queries). What is the name of this model? $\endgroup$ – Erel Segal-Halevi Jul 9 '20 at 8:20
  • 1
    $\begingroup$ The most popular models are the Real RAM and BSS. Your model sounds more like Real RAM, which is popular in computational geometry. $\endgroup$ – Yuval Filmus Jul 9 '20 at 8:26
  • $\begingroup$ @YuvalFilmus OK, so I am looking for bounds on the number of queries in the real RAM model. Do you know of some introductory references for this topic? (Google Scholar search yields only some advanced papers that appear unrelated..) $\endgroup$ – Erel Segal-Halevi Jul 9 '20 at 8:44

Your Answer

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

Browse other questions tagged or ask your own question.