Let $p \colon \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ be a one-dimensional function that fulfills $p(0)=0$. Moreover, we are given some value $u \in \mathbb{R}_{> 0}$ such that $p$ is strictly convex, increasing, and continuous on the interval $[0,u]$.

Assume that we can compute $p(x)$ on $[0,u]$ and the inverse function $p^{-1}(y)$ on $[0,p(u)]$ exactly with indefinite precision via oracle calls. We assume that we are in the Blum-Shub-Smale model, in which we can handle real numbers within arbitrary precision.

That's all we have for $p$. The question is: Can we use the oracles for $p$ and $p^{-1}$ in order to solve an equation of the form $p(x) = x+c$ for some real $c > 0$ ? (that's what I mean with "shifted fix point") We are only interested in solutions in the interval $[0,u]$ and we know that there is one such solution (which is uniquely defined, as one can easily see).

Is there any possibility or is the problem uncomputable in the BSS model for general functions $p$ ?

As I know from this question, already equations of the form $x^2 - 2 = 0$ are not solvable even in the BSS model, such that $p(x) = x+c$ would not be possible to solve for $p(x) = x^2+x$ and $c=2$ without any further assumptions. However, it might still be possible to use the oracles in some elegant way in order to solve the equation.


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.