6

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?

flag
1 
 Wouldn't that immediately yield $P\neq NP$? (Unless the inverse significantly increase the length of $n$...) – darij grinberg Jun 21 2011 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 2011 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 2011 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 2011 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 2011 at 12:28

1 Answer

12

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.

link|flag
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 2011 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 2011 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 2011 at 22:53
I agree with that. – Joel David Hamkins Jun 21 2011 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. – Frank Jun 27 2011 at 13:38

Your Answer

Get an OpenID
or

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