# 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 '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
• 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
• 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
• 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