1
$\begingroup$
  1. Given a polynomially computable continuous function which is a composite of m strictly monotone functions, can we guarantee the existence of polynomially computable inverse?

  2. The function I have in mind is a rational function and all the coefficients (in the numerator and denominator) are positive integers but are unknown. I realize that for strictly monotone functions, as long as it is honest (arbitrarily long fractions don't get mapped to short ones - are rational functions honest?) a binary search algorithm will find the inverse. But in case of existence of m maxima and minima, how to devise an appropriate algorithm that won't get stuck?

  3. We are of course restricting the function to $\mathbb{Q}\to \mathbb{Q}$ and for a given $q\in \mathbb{Q}$, for our purposes, it will suffice to have a polynomial time algorithm to find the minimum (maximum) approximate rational pre-image, where the error $\epsilon$ can be made arbitrarily small in time polynomial in $\epsilon^{-1}$.

$\endgroup$
  • 1
    $\begingroup$ What do you think? What research have you done? We normally expect you to flesh out your question more. In particular, I expect you to do research on your own before asking, and to show us in the question what research you've done. Also, please make sure that the body of the question is self-contained and I don't need to read the title to understand the question (perhaps pick a shorter title). P.S. What do you mean by a poly-computable function on $[0,1]$? Turing machines are discrete and cannot accept real numbers (continuous inputs) on their input tape, so this needs careful definition. $\endgroup$ – D.W. Sep 17 '14 at 3:37
  • $\begingroup$ Apologies - I am new to this place. I added a few things to the question to make it clearer. $\endgroup$ – Daniels Pictures Sep 17 '14 at 4:00
  • $\begingroup$ Your question is not very consistent and complete. - First, you mentioned differentiable but you didn't say to what order. - Secondly, you mentioned coefficients but you have to give us the model/class of your functions. From what you have written here perhaps you want something in the form of $f(x)/g(x)$ where $f(x)$ and $g(x)$ are polynomials? - Third, you realized that for a monotonic function, you can do binary search, but then you mentioned in the title "turning points" which most people will reasonably assume non-monotone $\endgroup$ – InformedA Sep 17 '14 at 4:06
  • $\begingroup$ Forth, you mentioned you want error bound of $\epsilon$ and want time bounded by $\epsilon^{-1}$ and you say binary search will work. So normally you would just divide your interval into multiple $\epsilon$ and then do binary search on that clearly poly on $\epsilon^{-1}$. Which comes to: What is your question? $\endgroup$ – InformedA Sep 17 '14 at 4:06
  • $\begingroup$ About your question about honest rational functions. The typical objective answer is some are and some are not. Some are in certain situation and some are not in certain situation. $\endgroup$ – InformedA Sep 17 '14 at 4:15

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.