Suppose we have a polynomial time algorithm for computing a function (we think of as existing on rational numbers between $0$ and $1$ of limited binary length n). We know that this function is made up of $m$ strictly monotone functions or equivalently that it has up to $m-1$ maxima/minima. Can we find these maxima in time that is polynomial in $m$ and $n$?
1
$\begingroup$
$\endgroup$
-
$\begingroup$ What are your thoughts? What have you tried? P.S. I'm not sure what you mean by "existing on rational numbers of limited binary length $n$"; you might like to try to state that more precisely. $\endgroup$ – D.W.♦ Sep 21 '14 at 5:27
1
$\begingroup$
$\endgroup$
Hint: Consider a function that is increasing, except in the small interval $[a,a+\varepsilon]$, where it decreases slowly. Assume $\varepsilon>0$ is very small and the value $a$ is not known a priori. Can you find the maxima in polynomial time?
