<p>There have been papers on automatically converting algorithms for bijective functions into algorithms for the inverse function; <a href="http://www.ics.uci.edu/~eppstein/pubs/Epp-IJCAI-85.pdf" rel="noreferrer">my own first conference paper</a> was one such. But the class of algorithms that can be inverted in this way is severely limited, as the other answers already suggest.</p>

CC BY-SA 2.5
2010-08-18T02:47:24.173Z
2010-08-18T02:47:24.173Z
David Eppstein
<p>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.</p>

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

CC BY-SA 2.5
2010-08-29T05:49:54.717Z
@Alexandru: The way I stated it, you are correct.  But consider the restriction of multiplication to the set D = {(p,x) : p is prime and at most the size of any prime divisor of x}.  The restricted map *:D \to {n > 1} is now bijective, and inverting it would allow you to factor.  Or, if you don't like that example, consider restricting the inputs to consist only of pairs of primes; integer multiplication restricted to this domain is injective, so is bijective onto its image (namely, numbers of the form $pq$ or $p^2$).  Inverting that would still allow you to break RSA.
Joshua Grochow
CC BY-SA 2.5
2010-08-18T02:01:21.243Z
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.
Kendall Hopkins
CC BY-SA 2.5
2010-08-18T02:09:03.847Z
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?
Kendall Hopkins
CC BY-SA 2.5
2010-08-18T02:37:01.360Z
You could use dovetailing to avoid that infinite loop issue.
http://en.wikipedia.org/wiki/Dovetailing_%28computer_science%29
Aaron Sterling
CC BY-SA 2.5
2010-08-18T02:43:04.263Z
@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).
Kendall Hopkins
CC BY-SA 2.5
2010-08-18T03:12:40.530Z
Integer multiplication is not bijective so your note is offtopic here.
Alexandru
CC BY-SA 2.5
2010-08-18T01:51:32.467Z
2010-08-18T01:51:32.467Z
Joshua Grochow
<p>As many on this page have already pointed out the solution in general could be intractable.</p>

<p>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. </p>

<p>An example of this approach (using Haskell) is explained in this paper
<a href="http://www.cs.ru.nl/A.vanWeelden/bi-arrows/" rel="nofollow">http://www.cs.ru.nl/A.vanWeelden/bi-arrows/</a></p>

<p>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).</p>

CC BY-SA 2.5
2010-08-18T03:36:05.520Z
2010-08-18T03:36:05.520Z
Jonathan Fischoff
<p>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).</p>

CC BY-SA 2.5
2010-08-18T02:38:05.540Z
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.
Kendall Hopkins
CC BY-SA 2.5
2010-08-18T02:58:47.267Z
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?
Lev Reyzin
CC BY-SA 2.5
2010-08-18T03:32:46.813Z
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.
Kendall Hopkins
CC BY-SA 2.5
2010-08-18T02:29:49.897Z
2010-08-18T02:29:49.897Z
Lev Reyzin
<p>Here's a handwavy algorithm under some strong assumptions.</p>

<h3>Assumptions</h3>

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

<p>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. </p>

<p>Note that this won't work for factoring, because multiplication is not bijective. Multiplication of primes <strong>is</strong>, 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.</p>

CC BY-SA 2.5
2010-08-18T03:05:59.823Z
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.
Kendall Hopkins
CC BY-SA 2.5
2010-08-18T03:06:59.557Z
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?
Evgenij Thorstensen
CC BY-SA 2.5
2010-08-18T03:18:09.800Z
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).
Kendall Hopkins
CC BY-SA 2.5
2010-08-18T03:31:10.633Z
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.
Evgenij Thorstensen
CC BY-SA 2.5
2010-08-18T04:18:25.863Z
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.
Kendall Hopkins
CC BY-SA 2.5
2010-08-18T02:50:40.000Z
2010-08-18T02:50:40.000Z
Evgenij Thorstensen
<p><strong>Does there exist a generalized algorithm for finding the inverse function of an arbitrary bijective function?</strong></p>

<ul>
<li>In order for this algorithm to be
useful, it must eventually halt once
the correct answer is found.</li>
<li>Beyond the requirement that it must find the solution eventually, there is <strong>no</strong> 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). </li>
</ul>

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

<p>EDIT:</p>

<p>I really liked Evgenij Thorstensen assumptions as they summed up my question fairly well.</p>

<p><strong>Assumptions</strong></p>

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

<p><strong>Another shot at explaining it:</strong></p>

<p>Given: Bijective function <code>F</code> that maps X from domain A onto Y from domain B.</p>

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

CC BY-SA 2.5
2010-08-18T01:36:59.617Z
what form is the input to the algorithm?
Lev Reyzin
CC BY-SA 2.5
2010-08-18T01:45:07.490Z
How could the form of the input change the existence of a solution?
Kendall Hopkins
CC BY-SA 2.5
2010-08-18T01:52:52.823Z
One-way permutations are believed to exist (e.g., RSA).  I suppose you are looking for negative results?
arnab
CC BY-SA 2.5
2010-08-18T01:57:30.877Z
@arnab The functions in question are bijective which by definition have inverse functions. I'm asking for a way of finding the known-to-exist inverse function.
Kendall Hopkins
CC BY-SA 2.5
2010-08-18T02:03:23.967Z
@Kendall: Ah, so you don't care about efficiency?  As Josh answered, there is always the trivial brute force algorithm (which is optimal in general).
arnab
CC BY-SA 2.5
2010-08-18T02:09:56.107Z
as a side note, if you're going to downvote, it would be helpful to explain why
Suresh Venkat
CC BY-SA 2.5
2010-08-18T02:51:04.680Z
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.
Aaron Sterling
CC BY-SA 2.5
2010-08-18T02:59:53.537Z
I agree with Aaron.  Also, it seems that Kendall is interested in efficiency, whereas this is not specified in the question.
Lev Reyzin
CC BY-SA 2.5
2010-08-18T03:35:11.307Z
@Lev Reyzin I don't care about efficiency, but bruteforce seems too useless to have any reasonable application and is boring to think about.
Kendall Hopkins
CC BY-SA 2.5
2010-08-18T03:42:07.517Z
@Kendall Hopkins I don't see how you can say you don't care about efficiency but then be unhappy with brute search. If you're actually happy with any algorithm, then @Joshua Grochow's brute force solution seems to work, especially as according to your new problem definition, the TM that computes the bijective function should always halt on valid domain.
Lev Reyzin
CC BY-SA 2.5
2010-08-18T04:06:04.653Z
@Lev Reyzin I'm unhappy with the bruteforce solution because you can't ensure that checking an attempt (even if it's right one) will halt. Think about a bijective function (identity) that would map real numbers to itself (1->1, e->e, etc). The inverse for this function is very obvious (itself). It would be impossible to valid this function is correct for all input because domain is continuous and it would never halt on a solution.
Kendall Hopkins
<ds.algorithms>
Algorithm for inverting a bijective function.
Kendall Hopkins
# Algorithm for inverting a bijective function.

(Asked by: username_0 on 2010-08-18)

**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.

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: what form is the input to the algorithm?  
> **username_0**: How could the form of the input change the existence of a solution?  
> **username_2**: One-way permutations are believed to exist (e.g., RSA).  I suppose you are looking for negative results?  
> **username_0**: @arnab The functions in question are bijective which by definition have inverse functions. I'm asking for a way of finding the known-to-exist inverse function.  
> **username_2**: @Kendall: Ah, so you don't care about efficiency?  As Josh answered, there is always the trivial brute force algorithm (which is optimal in general).  
> **username_3**: as a side note, if you're going to downvote, it would be helpful to explain why  
> **username_4**: 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.  
> **username_1**: I agree with Aaron.  Also, it seems that Kendall is interested in efficiency, whereas this is not specified in the question.  
> **username_0**: @Lev Reyzin I don't care about efficiency, but bruteforce seems too useless to have any reasonable application and is boring to think about.  
> **username_1**: @Kendall Hopkins I don't see how you can say you don't care about efficiency but then be unhappy with brute search. If you're actually happy with any algorithm, then @Joshua Grochow's brute force solution seems to work, especially as according to your new problem definition, the TM that computes the bijective function should always halt on valid domain.  
> **username_0**: @Lev Reyzin I'm unhappy with the bruteforce solution because you can't ensure that checking an attempt (even if it's right one) will halt. Think about a bijective function (identity) that would map real numbers to itself (1->1, e->e, etc). The inverse for this function is very obvious (itself). It would be impossible to valid this function is correct for all input because domain is continuous and it would never halt on a solution.  

---

## 5 answers

### Answer by username_5 on 2010-08-18. Score: 7 | Accepted answer

There have been papers on automatically converting algorithms for bijective functions into algorithms for the inverse function; [my own first conference paper](http://www.ics.uci.edu/~eppstein/pubs/Epp-IJCAI-85.pdf) was one such. But the class of algorithms that can be inverted in this way is severely limited, as the other answers already suggest.


---

### Answer by username_6 on 2010-08-18. Score: 4

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.)

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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?  
> **username_4**: You could use dovetailing to avoid that infinite loop issue. http://en.wikipedia.org/wiki/Dovetailing_%28computer_science%29  
> **username_0**: @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).  
> **username_7**: Integer multiplication is not bijective so your note is offtopic here.  
> **username_6**: @Alexandru: The way I stated it, you are correct.  But consider the restriction of multiplication to the set D = {(p,x) : p is prime and at most the size of any prime divisor of x}.  The restricted map *:D \to {n > 1} is now bijective, and inverting it would allow you to factor.  Or, if you don't like that example, consider restricting the inputs to consist only of pairs of primes; integer multiplication restricted to this domain is injective, so is bijective onto its image (namely, numbers of the form $pq$ or $p^2$).  Inverting that would still allow you to break RSA.  

---

### Answer by username_8 on 2010-08-18. Score: 3

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).


---

### Answer by username_1 on 2010-08-18. Score: 3

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).

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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?  
> **username_0**: 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.  

---

### Answer by username_9 on 2010-08-18. Score: 2

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.

> **Comments:**
> **username_0**: 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.  
> **username_9**: 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?  
> **username_0**: 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).  
> **username_9**: 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.  
> **username_0**: 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.  

---

