2
$\begingroup$

Let $f$ be a continuous real function on $[-1,1]$. The function is accessible via queries: for any $x$, the value of $f(x)$ can be computed in constant time. If $f(-1)<0$ and $f(1)>0$, then by the intermediate value theorem, $f$ has a zero --- an $x \in [-1,1]$ for which $f(x)=0$. Suppose we want to find a zero approximately, that is: given $\delta>0$, find an interval of length at most $\delta$, that contains a zero. This can be done using binary search: start with the entire interval $[-1,1]$; let $c$ be the middle of the interval; if $f(c)=0$ we are done; if $f(c)>0$ then recursively search between the leftmost end of the current interval and $c$; if $f(c)<0$ then recursively search between $c$ and the rightmost end. After $O(\log(1/\delta))$ steps, the interval length is at most $\delta$. So the run-time is polynomial in the length of the binary representation of $\delta$.

Now, suppose we have two continuous functions, $f$ and $g$, both defined on $[-1,1]\times[-1,1]$. Suppose $f(-1,y)<0$ for all $y$ and $f(1,y)>0$ for all $y$, and $g(x,-1)<0$ for all $x$ and $g(x,1)>0$ for all $x$. By the Poincare-Miranda theorem, there exists a double-zero, that is, a point $(x,y)\in[-1,1]\times[-1,1]$ such that $f(x,y)=g(x,y)=0$. We want to find a double-zero approximately, that is: given $\delta>0$, find a square of side-length at most $\delta$, that contains a double-zero. Is it possible to do in time $O(poly(\log(1/\delta))$?

I tried to apply binary search, but it did not work. If I could know, for example, that for some $c\in[-1,1]$, $f(c,y)<0$ for all $y$, then I could recursively search the rectangle $[c,1]\times[-1,1]$. But there is no reason to think that such a $c$ exists.

Can this problems be solved using $O(poly(\log(1/\delta))$ queries?

$\endgroup$

1 Answer 1

3
$\begingroup$

This paper studies a similar problem: finding an approximate fixed-point of a two-dimensional function from the unit square to itself, which is accessible via value queries. The authors prove that computing a fixed point with $p$ decimal digits requires $\Omega(2^p)$ queries. Equivalently, computing a square of side-length at most $\delta$ that contains a fixed point requires $\Omega(1/\delta)$ queries.


I claim that the same is true for finding a double-zero with general functions. The proof is by reduction from the fixed-point problem. Let $h$ be a continuous function for which we want to find a fixed point, and suppose it is a function on the square $[-1,1]^2$. Define two functions $f$ and $g$ as follows:

$$ f(x,y) := x - h(x,y)_1 \\ g(x,y) := y-h(x,y)_2 $$

Note that $$ f(-1,y) \leq (-1) - (-1) = 0 ~~~~ f(1,y) \geq 1 - 1 = 0 \\ g(x,-1) \leq (-1) - (-1) = 0 ~~~~ g(x,1) \geq 1 - 1 = 0, $$ so the pair $(f,g)$ has a double-zero. Moreover, $(x,y)$ is a double-zero of $(f,g)$ if and only if it is a fixed point of $h$. Therefore, finding an approximate double-zero requires $\Omega(1/\delta)$ queries.


For the case of monotone functions, I asked a separate question in cstheory.SE.

$\endgroup$
2
  • $\begingroup$ @YvesDaoust ??? An $\Omega(1/\delta)$ bound implies that an $O(\mathrm{poly}(\log(1/\delta)))$ bound does not hold, directly answering the question in the negative. $\endgroup$ Apr 4, 2023 at 10:54
  • $\begingroup$ Right, sorry, my bad. $\endgroup$
    – user16034
    Apr 4, 2023 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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