Specifically we know that for our function $f$ ($f$ takes real values), $\infty>f(0)>0$, while $-\infty<f(1)<0$. So the classical binary search will find an approximate zero within $\epsilon$ of the actual zero in time $\lceil\log_2(\epsilon^{-1})\rceil$, but what about all the other zeros? Again our algorithm has to be polynomial in $\epsilon^{-1}$ as well.

I guess in general the answer to this question must be 'no'. But if we know that the zeros are bounded away from the endpoints of the interval and each other by some fixed $\epsilon$, then it should be possible. We will then need to take $\delta < \epsilon$ and apply the binary search algorithm recursively to the subintervals marked by each approximate zero.

Does that sound right?

  • $\begingroup$ Is $f$ a computable real function or something more conventional? $\endgroup$ – Yuval Filmus Oct 16 '14 at 22:00
  • $\begingroup$ Also, suppose that $f(0) = f(1) = 1$. Is it decidable whether $f$ vanishes in $(0,1)$? $\endgroup$ – Yuval Filmus Oct 16 '14 at 22:01
  • $\begingroup$ f is polynomially computable rational function $p(x)/q(x)$ where $p$ and $q$ are polynomials with positive integer coefficients and degrees $\leq m$, but we don't know the coefficients. There is just some algorithm for computing the values of the function in time that is polynomial of $m$. So not sure if this information is helpful at all. $\endgroup$ – Daniels Pictures Oct 16 '14 at 22:04
  • $\begingroup$ So $f$ accepts a rational number and outputs a rational number? Also, what is your computation model? It seems for you arbitrary-precision arithmetic is for free (i.e., has unit cost). $\endgroup$ – Yuval Filmus Oct 16 '14 at 22:05
  • $\begingroup$ I guess, the answer to your question about f(0)=f(1)=1 must be 'no', since it could dip down to $0$ and back up in an arbitrarily small subinterval and in principle, this could happen in my case too, making such an algorithm impossible... $\endgroup$ – Daniels Pictures Oct 16 '14 at 22:08

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.