Re: Inversion of an algorithm

user923005 <dcorbit@xxxxxxxxx> writes:

On Apr 13, 2:27 pm, Ben Pfaff <b...@xxxxxxxxxxxxxxx> wrote:
user923005 <dcor...@xxxxxxxxx> writes:
On Apr 12, 2:09 pm, Ben Pfaff <b...@xxxxxxxxxxxxxxx> wrote:
Willem <wil...@xxxxxxxxxxxxxx> writes:
Jean Guillaume Pyraksos wrote:
) Say I have a one-one function f from a set A to a set B. I have
) an algorithm to compute f.
) Has anyone worked on getting *automatically* an algorithm for the
) inverse function from B to A ? Or is there a deep result about that ?
) Has this problem something to do with automatic differentiation ?
)
) f is *not* specifically a math function, but a recursive one on trees.

Functions usually don't have an inverse function.  Only a very special
subclass of functions do. (Injective, I believe they're called).

Jean already said that he knows that the function is injective
(injective and one-to-one are synonyms).

That, in itself, makes it impossible to automate generically.

It is trivial to invert a one-to-one function, given some ways of
describing the function.  For example, if the function is
described using a table, then you can just rearrange the table.

It is more difficult to invert one-to-one functions described
other ways.  So far, Jean hasn't told us any details of how his
algorithm is described, so it's hard to say how much more
difficult in his case.

One to one isn't good enough.  It also has to be onto.

Why?  If there are some values in the function's range that have
no corresponding value in its domain, those are just don't-cares
in the inverse function.  No?

For a concrete example that is interesting enough to consider, think
about the function:

double f(double x)
{
return pow( x, x );
}

Quite an interesting function, with a minimum at (1/e)^(1/e).

The domain we will consider is between (0 and 1].

Now, for every real-number value of x, there is exactly one value of
y. (We have lots of other nice things to say about this function on
this domain -- it is smooth, continuous, and differentiable).

However, when we rotate this function about the line y = x {the
classic eyeball test to see if a function is invertible} we will see
something that will make us unhappy if we want to invert it.
That unhappy finding is that for any y value between 1.0 and (1/e)^(1/
e) there are exactly two possible values of x that will produce it.
We don't know which one it came from.

That is an example of a function that is not one-to-one. No one was
questioning this case. Ben Pfaff was talking about one-to-one
functions that are not also onto. These are, it is true, not
invertible, but there is an obvious inverse implied by any such
function -- the inverse defined over the image of f rather than the
codomain of f. I think that is what he was getting at.

There is logical problem inverting a function that is not one-to-one
but only a problem of definition inverting a one-to-one function that
is not onto.

--
Ben.
.

Relevant Pages

  • Re: Inversion of an algorithm
    ... Has anyone worked on getting *automatically* an algorithm for the ... classic eyeball test to see if a function is invertible} we will see ... That unhappy finding is that for any y value between 1.0 and ^(1/ ... There is logical problem inverting a function that is not one-to-one ...
    (comp.programming)
  • Re: bilinear pairing between special groups
    ... for inverting the map ... efficient algorithm for finding the cyclic group of order q sitting ... This is not the discrete logarithm problem, since we do now know the ... could be done efficiently, but what happens with the bilinear pairing, ...
    (sci.math)
  • Re: VMPC function. Question on definition of inverting
    ... > algorithm fails to work well. ... fastest algorithm of inverting the function. ... I don't know to what extent my algorithm of inverting VMPC would be helpful. ... Bartosz Zoltak ...
    (sci.crypt)
  • Re: Inversion of an algorithm
    ... Has anyone worked on getting *automatically* an algorithm for the ... Functions usually don't have an inverse function. ... That, in itself, makes it impossible to automate generically. ... You all think I'm paranoid, ...
    (comp.programming)
  • Re: Inversion of an algorithm
    ... Jean Guillaume Pyraksos writes: ... Has anyone worked on getting *automatically* an algorithm for the ... inverse function from B to A? ... f is *not* specifically a math function, but a recursive one on trees. ...
    (comp.programming)