Existem classes de funções que exigem recursos comprovadamente diferentes para calcular versus calcular sua inversa?

Pedimos desculpas antecipadamente se esta pergunta for muito simples.

Basicamente, o que eu quero saber é se há alguma função com as seguintes propriedades:$f(x)$

Tome para ser quando o domínio e codomain são restritas a cadeias de bits. Entãof ( x ) $f_n(x)$$f(x)$$n$

1. $f_n(x)$ é injetivo
2. $f_n(x)$ é adjetivo
3. $f_n(x)$ consome estritamente menos recursos (espaço / tempo / profundidade do circuito / número de portas) para calcular sob algum modelo razoável que , onde .$f^{-1}_n(y)$$y=f_n(x)$
4. A diferença de recursos para vs escalada como uma função estritamente crescente de .$f_n(x)$$f^{-1}(y)$$n$

Posso apresentar exemplos em que a função é adjetiva ou injetiva, mas não ambos, a menos que eu recorra a um modelo computacional artificial. Se eu escolher um modelo computacional que permita mudanças à esquerda em unidade de tempo em algum anel, mas não mudanças à direita, é claro que é possível criar uma sobrecarga linear (ou superior, se você considerar uma permutação mais complicada como primitiva) . Por esse motivo, estou interessado apenas em modelos razoáveis, pelos quais quero dizer principalmente máquinas de Turing, circuitos NAND ou similares.

Obviamente, isso deve ser verdade se , mas parece que isso também é possível se , e, portanto, não deve ser uma decisão para essa pergunta.$P\neq NP$$P=NP$

É perfeitamente possível que essa pergunta tenha uma resposta óbvia ou um obstáculo óbvio à resposta que eu perdi.

Me pediram para repassar meu comentário. Eu apontei este artigo de Hastad, que mostra que existem permutações em que são difíceis de inverter:$NC^0$

http://dx.doi.org/10.1016/0020-0190(87)90053-6 (PS)

Para circuitos booleanos em uma base binária completa (com a medida de complexidade sendo o número de portas em um circuito mínimo), a razão mais conhecida para permutações . Até onde eu sei, a melhor constante foi obtida neste trabalho por Hiltgen e é igual a 2.C ( f - 1$C(f)$$\frac{C(f^{-1})}{C(f)} = const$

Editar. Como você deseja que a proporção aumente quando cresce, isso não responde à sua pergunta. No entanto, para circuitos booleanos em uma base binária completa, nada melhor é conhecido.$n$

Antes de tudo, eu queria ressaltar que a sujetividade não é bem definida sem antes definir o codomain da função. Então, na minha descrição abaixo, vou me referir explicitamente ao codomain sobre o qual a função é adjetiva.

Tanto o logaritmo discreto quanto as funções RSA são permutações que são conjecturadas por serem difíceis de inverter. Abaixo, descreverei a função de logaritmo discreto.

Seja um primo de n bits eg seja um gerador do grupo multiplicativo Z ∗ p n . Defina f n : Z p n → Z p n como f n ( x ) = g $p_n$$n$$g$$\mathbb{Z}_{p_n}^*$$f_n \colon \mathbb{Z}_{p_n} \to \mathbb{Z}_{p_n}$ .$f_n(x) = g^x \pmod{p_n}$

Então, é uma função cujas propriedades são as indicadas na sua pergunta: é ao mesmo tempo injetiva e adjetiva (sobre o codomain Z p n ), é computável em tempo polinomial, mas é conjecturado que nenhum algoritmo eficiente possa inverter f n em média.$f_n$$\mathbb{Z}_{p_n}$$f_n$