1
$\begingroup$

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$?

|cite|improve this question
$\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$

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?

|cite|improve this answer
$\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.