Polynomial time optimisation algorithm for a poly-time computable function with bounded number of maxima?
Hint: Consider a function that is increasing, except in the small interval $[a,a+\varepsilon]$, where it decreases slowly.  Assume $\varepsilon&gt;0$ is very small and the value $a$ is not known a priori.  Can you find the maxima in polynomial time?