2
$\begingroup$

A. Let $F$ be a monotonically increasing real function from $[0,1]$ onto $[0,1]$. Given an oracle to $F$ and a number $y$, is there a way to calculate the inverse function $F^{-1}(y)$ in a finite number of calls to the oracle?

I think the answer is no, because of a simple counting argument: there are uncountably many possible answers, and with a finite number of calls we can get only countably many answers. Is this correct?

B. Let $F, G$ be two functions as above, and let $H$ be their average: $H(x)=[F(x)+G(x)]/2$. Given an oracle to $F^{-1}$ and an oracle to $G^{-1}$ and a number $y$, is there a way to calculate $H^{-1}(y)$ in a finite number of calls?

I think the answer is no, but how can I formalize the counting argument?

Is this possible to reduce to this problem from problem A? Or from another problem which provably cannot be solved in finite time?

NOTE: It can be argued that any function on reals is inherently infinite because even the output of a real number might take infinite time. So for this question, assume that we have a computer that can input, output and do arithmetics on real numbers in constant time per operation.

similar question was posted in math.SE, no answers yet.

$\endgroup$
12
  • 2
    $\begingroup$ For (A) I concur with your reason, and it seems like a straightforward adversary argument, where you make any series of queries, and the adversary can pick a number that satisifies all the queries but is not the inverse. I think a similar argument could be constructed for (B). I'll have a go when I don't have to go catch a train ;) (or Yuval will get there first ;) anyway). $\endgroup$ – Luke Mathieson Apr 17 '15 at 7:45
  • 1
    $\begingroup$ Since you are defining $F^{-1}$, you must assume $F$ is strictly monotonically increasing, so as to be bijective (since onto). - - - - - The problem with using the traditional real in your question is not just that it takes infinite time to output, but more radically that it cannot be output by any Turing Machine. Is there a consistent theory about computability and algorithms over the traditional uncountable reals? Can you give a reference? $\endgroup$ – babou Apr 18 '15 at 11:00
  • $\begingroup$ @babou I am not aware of a theory about computability in reals. But what's wrong with just assuming that we have a computer with registers that can hold real numbers? $\endgroup$ – Erel Segal-Halevi Apr 18 '15 at 17:27
  • 2
    $\begingroup$ Because everything we know about computation is based on ultimate finiteness of definitions. In a real number, you can encode infinite information. So you can probably do otherwise infinite computations in one step. I am not expert enough to have a definite opinion without more work, but there is a distinct possibility that using reals that way makes anything computable. This is why I am asking whether there is a consistent theory, one in which some things are true and some others are false. You cannot take that for granted. What are your axioms. $\endgroup$ – babou Apr 18 '15 at 19:43
  • 2
    $\begingroup$ Regarding the use of reals, maybe you could wonder whether you can get a given approximation in finite time. This should be possible, I conjecture. The issue though might be whether you can do that uniformly, i.e. whether you can have the same upperbound on the time needed for a given approximation everywhere on the interval. I suspect that this depends on differential properties of the function $F$ (not meaning to imply that it has to be derivable). But I am not sure what you are trying to get at. $\endgroup$ – babou May 1 '15 at 12:41
1
$\begingroup$

I am skipping the first question, question A, as it is not clear to me how it can make sense formally, since I am not familiar with the formalizations the OP mentions in a comment: Are there established complexity classes with real numbers?

I am only adressing the relation between question A and question B, proving that question B can be reduced to question A, which the OP considers of interest in itself. And since we are supposed to deal with only one question at a time, this follows the local rules. :)

Question B reduces to question A : B ≤ A

First I will rephrase both questions, so as to add a missing hypothesis (bijectivity of the function, though existence of an inverse implies it), and also to use notations that will make the proof easier to state.

Question A: Let $F$ be a bijective, monotonically increasing real function from $[0,1]$ onto $[0,1]$. Given an oracle to compute $F$ on any input and a number $y\in[0,1]$, is there a way to calculate the inverse function $F^{-1}(y)$ in a finite number of calls to the $F$ oracle?

Question B: Let $H, K$ be two functions like $F$ above, and let $G$ be their average: $G(x)=[H(x)+K(x)]/2$. Given an oracle to compute $H^{-1}$ and an oracle to compute $K^{-1}$ and a number $y\in[0,1]$, is there a way to calculate $G^{-1}(y)$ in a finite number of calls to the $H$ and $K$ oracles.?

Note: all functions considered are bijective monotonic, but for readability we leave implicit the related arguments, though they do matter in some of the inferences below.

The idea of the proof is that, if $x=G^{-1}(y)$ is a solution to problem B, then there are two numbers $h,k\in[0,1]$ such that

  1. $y=(h+k)/2$, and

  2. $h=H(x)$, and $k=K(x)$ for some $x\in [0,1]$

We try to resolve the problem by defining a variable $u\in[0,1]$, so that $h$ and $k$ are computed from $u$ to take all possible values while $u$ varies from $0$ to $1$.

From $y=(h+k)/2$ we get $h+k=2y$. So we define: $h_u=2yu$ and $k_u=2y(1-u)$.
This ensures that $y=(h_u+k_u)/2$, but will let $h_u$ or $k_u$ become greater than $1$ when $y$ is greater than $1/2$.

So, we must actually consider two somewhat similar cases, depending on the value of $y$, after noting that $h_u$ and $k_u$ are both monotonically increasing functions of $u$.

case 1: $y\leq 1/2$

What we want is to find $h$ and $k$ such that $h=H(x)$ and $k=K(x)$ for some value $x$.

We define the function $D(u)=H^{-1}(h_u)-K^{-1}(k_u)=H^{-1}(2yu)-K^{-1}(2y(1-u))$
Note that $H^{-1}(0)=K^{-1}(0)=0$.
Hence $D(0)=H^{-1}(0)-K^{-1}(2y)=-K^{-1}(2y)$,
and $D(1)=H^{-1}(2y)-K^{-1}(0)=H^{-1}(2y)$.

So the function $D(u)$ is increasing onto $[-K^{-1}(2y),H^{-1}(2y)]$, and the solution to finding the value of $u$ that corresponds to the right values of $h$ and $k$ is given by the equation $D(u)=0$.

However, we intend to resolve it using an algorithm to solve question A, so we must normalize the interval to make it $[0,1]$.

For that we define $F(u)=\frac{D(u)+K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}$
The function $F$ satisfies the conditions of question A,
and we remark that $D(u)=0$ iff $F(u)=\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}$.
So we have to compute $u_0=F^{-1}(\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)})$, which can be done using the algorithm answering question A. Then $G^{-1}(y)=H^{-1}(2yu_0)$, or to summarize in one formula:

$$G^{-1}(y)=H^{-1}(2yF^{-1}(\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}))$$

Each computation of $F(u)$ uses only a finite (small) number of calls to the oracles for $H^{-1}$ and $K^{-1}$. Thus a solution to question B can be computed with a finite number of oracle calls if that is the case for problem A.

case 2: $y>1/2$

This case is a bit more complicated, as different bounds must be found for varying $u$ so that $h$ and $k$ do not get greater than $1$, since the functions $H$ and $K$ are defined only onto $[0,1]$.

Since $y=(h_u+k_u)/2$, we have $h_u=2y-k_u$. Thus, $k_u\leq 1$ implies $h_u\geq 2y-1$.

The same reasonning holds, exchanging $h$ and $k$, so that we have $h_u,k_u\in [2y-1, 1]$. Since $u=h_u/(2y)$, we have $u\in[u_0,u_1]$ with $u_0=1-1/(2y)$ and $u_1=1/(2y)$.

In order to have a variable $v$ varying in $[0,1]$, we normalize by defining $v=(u-u_0)/(u_1-u_0)$. But $u_1-u_0=1/(2y)-(1-1/(2y))=(1-y)/y$ which gives $v=(u-u_0)y/(1-y)$. Hence, with $u=v(1-y)/y+u_0$, $u$ is a function of $v$ monotonically increasing onto $[u_0,u_1]$ when $v\in[0,1]$.

Thus, considering $h$ and $k$ as functions of $v$ we have $h_v=2y(v(1-y)/y+u_0)$ and $k_v=2y(1-(v(1-y)/y+u_0))$, with $u_0=1-1/(2y)$

Simplifying we get $h_v=2y-1+2v(1-y)$ and $k_v=1-2v(1-y)$, for $v\in[0,1]$

From here on the reasonning is the same as for the first case, since monotonically increasing functions are closed under composition, the variable being $v$ rather than $u$, considering the function: $D(v)=H^{-1}(h_v)-K^{-1}(k_v)=H^{-1}(2y-1+2v(1-y))-K^{-1}(1-2v(1-y))$

I hope that there is no error in symbol manipulations, but the line of reasonning should not be affected if that were the case.

The proof can be simplified by using a lemma that generalizes the question A, which is here a hypothesis, to any strictly increasing function from any closed interval to any other closed interval.

$\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.