8
$\begingroup$

Does there exist a generalized algorithm for finding the inverse function of an arbitrary bijective function?

  • In order for this algorithm to be useful, it must eventually halt once the correct answer is found.
  • Beyond the requirement that it must find the solution eventually, there is no time constraints on the time it takes to find or run the inverse function (with that in mind, something better than bruteforce guess-and-check, would be more interesting).

For example, if such a generalized algorithm existed it could solve for a decompression algorithm for a lossless compression algorithm.

EDIT:

I really liked Evgenij Thorstensen assumptions as they summed up my question fairly well.

Assumptions

  • Computable bijective functions over a fixed alphabet (say {0, 1})
  • Represented by a deterministic Turing machine (DTM) that computes it
  • The proposed algorithm would be able to solve for a DTM that would invert the original bijective function output.

Another shot at explaining it:

Given: Bijective function F that maps X from domain A onto Y from domain B.

Proposed algorithm should be able to solve for a Bijective function G that maps Y from domain B onto X from domain A, such that G(F(X))=X and F * G = I where I is the identity function.

Improve this question
$\endgroup$
11
  • $\begingroup$ what form is the input to the algorithm? $\endgroup$
    – Lev Reyzin ♦
    Aug 18, 2010 at 1:36
  • $\begingroup$ How could the form of the input change the existence of a solution? $\endgroup$
    – Kendall Hopkins
    Aug 18, 2010 at 1:45
  • 1
    $\begingroup$ One-way permutations are believed to exist (e.g., RSA). I suppose you are looking for negative results? $\endgroup$
    – arnab
    Aug 18, 2010 at 1:52
  • 2
    $\begingroup$ as a side note, if you're going to downvote, it would be helpful to explain why $\endgroup$
    – Suresh Venkat
    Aug 18, 2010 at 2:09
  • 2
    $\begingroup$ I just downvoted because this question is not sufficiently specified to provide a concrete answer. Too vague. To improve: what is the precise input to the algorithm, and what is the precise output of the algorithm? Otherwise, we're just guessing at what you might mean. $\endgroup$
    – Aaron Sterling
    Aug 18, 2010 at 2:51

5 Answers 5

Reset to default
7
$\begingroup$

There have been papers on automatically converting algorithms for bijective functions into algorithms for the inverse function; my own first conference paper was one such. But the class of algorithms that can be inverted in this way is severely limited, as the other answers already suggest.

Improve this answer
$\endgroup$
4
$\begingroup$

Over a completely unstructured domain, the best you can do is brute force search, which takes time linear in the size of the domain. However, if the domain you're talking about is n-bit strings, that's exponential in n.

(Note that, if there were an efficient fully general function inverter, then inverting the integer multiplication function would give you an efficient factoring algorithm.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ It wouldn't have to be efficient. Just because an algorithm to invert any given bijective function, doesn't say anything about that function's inverse. For example, compression/decompression. $\endgroup$
    – Kendall Hopkins
    Aug 18, 2010 at 2:01
  • $\begingroup$ I also think you could have problems with the halting problem if you were simply bruteforcing a solution. Since each attempt would have to be checked for correctness (run). What if one of the brute force attempts infinite looped? What if the solution takes infinity time to run? $\endgroup$
    – Kendall Hopkins
    Aug 18, 2010 at 2:09
  • $\begingroup$ You could use dovetailing to avoid that infinite loop issue. en.wikipedia.org/wiki/Dovetailing_%28computer_science%29 $\endgroup$
    – Aaron Sterling
    Aug 18, 2010 at 2:37
  • $\begingroup$ @Aaron Very interesting solution for the infinite loop. I believe it still doesn't solve the problem if correct solution would take infinite time to run (though the usefulness of such a solution is questionable). $\endgroup$
    – Kendall Hopkins
    Aug 18, 2010 at 2:43
  • 1
    $\begingroup$ Integer multiplication is not bijective so your note is offtopic here. $\endgroup$
    – Alexandru
    Aug 18, 2010 at 3:12
3
$\begingroup$

As @arnab pointed out in the comments, one-way permutations are a cryptographic primitive. If you want to invert arbitrary functions efficiently, you will have cryptographic barriers to overcome (in addition to factoring).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I'm pretty sure a "generalized" cryptographic function isn't Bijective because using different keys/data you could end up with the same data (unlikely, but still possible). If you given a cryptographic function with a preset key, the generalized algorithm would just have to solve for an algorithm that could bruteforce the private key (factoring the public), it wouldn't have to bruteforce itself. $\endgroup$
    – Kendall Hopkins
    Aug 18, 2010 at 2:38
  • $\begingroup$ RE "the generalized algorithm would just have to solve for an algorithm that could bruteforce the private key" -- I am not sure I understand you. All else aside, how is brute forcing a key efficient? $\endgroup$
    – Lev Reyzin ♦
    Aug 18, 2010 at 2:58
  • $\begingroup$ The question is only asking for an algorithm that finds an algorthm for solving the problem, it doesn't have to solve it, and the inverting-solution nor the inverting-finding-solution have ANY time constraint on them. $\endgroup$
    – Kendall Hopkins
    Aug 18, 2010 at 3:32
3
$\begingroup$

As many on this page have already pointed out the solution in general could be intractable.

All is not lost if you are interested in invertible programming. An alternative to finding the inverse for a given function, is to construct your function from the composition of invertible functions, in which case finding the inverse is trivial.

An example of this approach (using Haskell) is explained in this paper http://www.cs.ru.nl/A.vanWeelden/bi-arrows/

As it so happens I have used Biarrow's to help me write only one direction of a compression algorithm and get the other (decompression) for free (free might be the wrong word, they are awkward to use, because of the lack of language support).

Improve this answer
$\endgroup$
2
$\begingroup$

Here's a handwavy algorithm under some strong assumptions.

Assumptions

  • Computable bijective functions over a fixed alphabet (say {0, 1})
  • Represented by a deterministic Turing machine (DTM) that computes it and not something "more" (see below)
  • If the input DTM doesn't compute a bijective function, we don't care what happens

With these assumptions, we can look at the input DTM, and invert all transitions (halting states become start states, reading becomes writing and vica versa, we read from the end, left is right, etc). Since the TM is deterministic and the function computed is bijective, the result is also a TM, and computes the inverse.

Note that this won't work for factoring, because multiplication is not bijective. Multiplication of primes is, if we disregard order, but a TM that multiplies numbers does not compute "only" the bijective function we want, it computes "too much", hence my second assumption (yes, it is rather strong). This ties nicely in with the comments about representation.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'm not sure you just "invert" a DTM by the description you gave. That would work for a regular grammar but not a DTM. $\endgroup$
    – Kendall Hopkins
    Aug 18, 2010 at 3:05
  • $\begingroup$ This should furthermore be linear in the size of the input. Ah, how useful these strong assumptions. Why do you think it won't work for a DTM? $\endgroup$
    – Evgenij Thorstensen
    Aug 18, 2010 at 3:06
  • $\begingroup$ A turning machine can't run in reverse (which is what I think your asking for). When your at a state, symbol and position, you don't know what event caused you to get there (as you can end up at the same position/state/symbol more than one way). $\endgroup$
    – Kendall Hopkins
    Aug 18, 2010 at 3:18
  • $\begingroup$ An arbitrary DTM can't, but I was trying to use the assumption that it computes (actually, represents) a bijective function. If we are at a state, symbol, and position, out of all the paths that lead here, only one could have written what we are now reading (since we are talking about inverses), otherwise it's not a representation of a bijective function. I guess my assumption about bijectiveness is precisely that there's a unique path. $\endgroup$
    – Evgenij Thorstensen
    Aug 18, 2010 at 3:31
  • $\begingroup$ I'm pretty sure that's incorrect, think about the encryption (with a preset pub key) example given here. It's a bijective function, but you can't just "walk" backwards on an encryption algorithm (kinda the point). Which makes me conclude that you can't do the same thing for a bijective DTM. $\endgroup$
    – Kendall Hopkins
    Aug 18, 2010 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.