## The hardness of computing inverse

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?

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

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.

-