Apologies in advance if this question is too simple.Basically, what I want to know is if there are any functions $f(x)$ with the following properties:Take $f_n(x)$ to be $f(x)$ when the domain and codomain are restricted to $n$-bit strings. Then$f_n(x)$ is injective$f_n(x)$ is surjective$f_n(x)$ takes strictly less resources (either space/time/circuit depth/number of gates) to compute under some reasonable model than $f^{-1}_n(y)$, where $y=f_n(x)$.The resource difference for $f_n(x)$ vs $f^{-1}(y)$ scales as some strictly increasing function of $n$.I can come up with examples where the function is either surjective or injective, but not both unless I resort to a contrived computational model. If I choose a computational model which allows left shifts in unit time on some ring, but not right shifts, then it is of course possible to come up with a linear over head (or higher if you consider some more complicated permutation as a primitive). For this reason I am interested only in reasonable models, by which I mostly mean Turing machines or NAND circuits or similar. Obviously this must be true if $P\neq NP$, but it would seem that this is also possible if $P=NP$, and so should not amount to deciding that question.It is entirely possible that this question has an obvious answer or an obvious obstacle to answering which I have missed.
Are there any classes of functions which require provably different resources to compute versus computing their inverse?
cc.complexity theory
I was asked to repost my comment.  I pointed out this paper by Hastad, which shows that there exist permutations in $NC^0$ that are P-hard to invert:http://dx.doi.org/10.1016/0020-0190(87)90053-6 (PS)