Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input.

Are there functions $f$ that are computable in polynomial time but whose inverse is known not to be computable in polynomial time?

Does the situation change if we drop the one-to-one requirement and define the inverse as, say, min$(f^{-1})$? How about if we change the complexity class in question?

share|improve this question
1  
Wouldn't that immediately yield $P\neq NP$? (Unless the inverse significantly increase the length of $n$...) –  darij grinberg Jun 21 '11 at 7:07
    
Known? Don't know. Unlikely to be known? Try an appropriate encoding that computes the encoded equivalent of f(G,k,p) = G if p is a Hamiltonian path through G of length at most k, and 0 otherwise. There are probably ways to tweak this to get something 1-1. Also, you can probably get something similar for most interesting complexity classes. Gerhard "Email Me About System Design" Paseman, 2011.06.21 –  Gerhard Paseman Jun 21 '11 at 7:15
3  
The concept is closely related to that of a one-way function, whose existence would imply $\mathrm{P}\ne\mathrm{NP}$. Link: en.wikipedia.org/wiki/One-way_function –  Jesko Hüttenhain Jun 21 '11 at 9:06
3  
Note that the definition of one-way function on Wikipedia is missing an often overlooked key requirement: honesty - that the length of the output must be nearly equal to some polynomial of the length of the input. As Joel's example shows, this requirement is essential... –  François G. Dorais Jun 21 '11 at 11:39
2  
So it appears that, short of a proof of $P\neq NP$, we will have only dishonest answers to this question! :-) –  Joel David Hamkins Jun 21 '11 at 12:28

1 Answer 1

up vote 13 down vote accepted

Here is an example of a total injective function $f:\mathbb{N}\to\mathbb{N}$, which is computable in polynomial time, but whose inverse function is not even computable, let alone polynomial-time computable. The idea is simply that we treat the input $n$ as a existential witness for some undecidable property of a smaller number $k$, such as the halting problem. Since these witnesses can and indeed must become very large, the inverse function, as Darij expected, will have large blow-up in size.

Let $f(n)=2k$ if $n$ is the code, in some highly canonical way, of a sequence of Turing machine configurations of the complete computation of program $k$ on input $0$ showing it to halt. Otherwise, if $n$ is not such a code, we let $f(n)=2n+1$.

This function is easily computable, in low-degree polynomial time, since we can check if $n$ is such a code easily and then give the corresponding output. The function is total and injective, since we give even output in the first case, in which case $n$ is determined by $k$ since we are using canonical codes, and $k$ is determined by $2k$, and we give odd output in the second case, in which case $n$ is again determined by $2n+1$.

But meanwhile, the inverse function is not computable at all, let alone in polynomial time, since we cannot tell whether $2k$ is in the range of the function unless we know whether $k$ halts on input $0$, which would solve the halting problem.

One can use essentially the same idea to give a direct non-polynomial time example. Namely, let $g(1^{2^k})= 1^{2k}$, meaning sequences of $1$s, and $g(n)=1^{2n+1}$, if $n$ is not a sequence of $1$s of length a power of $2$. We can compute $g$ in polynomial time, but the inverse function takes exponential time.

share|improve this answer
    
But there is a very simple computable partial function which, restricted to f's range, acts as the desired inverse (in the sense of a left inverse, which is presumably all that was wanted, as the function to be "inverted" was not stipulated to be surjective); it's not really the inversion here which is difficult, but deciding the range. That seems potentially a little off from the spirit of the question; I can easily imagine the questioner's idea of "computable inverse" being "There is a computable partial function which acts as a left inverse". –  Sridhar Ramesh Jun 21 '11 at 18:14
    
Yes, and my example shows the need for a careful treatment of the properties in the question (like the honesty requirement). Nevertheless, I don't agree with your view that it is only the computation of the values of a function that is important, rather than the domain or range, since often the range of the function contains the most important information, such as is the case with the c.e. sets, for example. We wouldn't say that every set is essentially c.e., just because the always-say-yes function gets the right answer when restricted to that set. –  Joel David Hamkins Jun 21 '11 at 18:18
    
It's not my view that it's only ever the computation of the values of a function that's important, rather than the domain or range. What's important is context-dependent; I was only expressing concern that, in this particular case, what the question-asker was asking for had an ambiguity which may not have been interpreted in the desired manner of the question-asker. That having been said, there was the polytime constraint, which I now realize makes your example sufficient regardless, since any polytime partial left inverse extends to a total one, and thus we could decide the range. –  Sridhar Ramesh Jun 21 '11 at 22:53
    
I agree with that. –  Joel David Hamkins Jun 21 '11 at 23:50
    
@Sridhar You are correct in your comments in the sense that I might have formulated the question differently if I had the insight I now have. This question arose from something completely different and I placed it here just to gain some understanding over the issue with the help of experts in the field. I would formulate it more carefully now. Joel did, however, provide an excellent answer that clarified the basic issues (like honest function) to me. –  user10891 Jun 27 '11 at 13:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.