Demostrar que una función es una función trampa

Question

Estoy trabajando en un problema que implica una aplicación iterativa de una función que creo que podría ser una función trampilla.

Formalmente, tengo una función $f:X \to X$ que puede describirse como

$$[x_{1,N+1}, ..., x_{s,N+1}]=f([x_{1,N},...,x_{s,N}])\\ \forall_{i<s-1}x_{i,N}=x_{i+1,N+1}$$ y $x_{s, N+1}$ se muestrea probabilísticamente y corresponde a un vector entero de dimensión alta.

Si conocemos el estado inicial de la función ( $[x_{1,0},...,x_{s,0}]$ ), el cálculo de la propagación hacia delante de la función es sencillo y podemos llegar a $[x_{1,N},...,x_{s,N}]$ realizando $f \circ f$ $N$ veces, lo que significa que para N<s, podemos verificar fácilmente que la secuencia [x_{1,N}, ..., x_{s,N}] fue efectivamente muestreada por $f$ .

Sin embargo, sin ( $[x_{1,0},...,x_{s,0}]$ ), no hay otra forma trivial de revertir la función que muestrear todos los valores posibles para $x_{1,N}$ .

Tengo la corazonada de que si $f$ fuera determinista, correspondería a una función de trampilla, con $[x_{1,0},...,x_{s,0}]$ actuando como un secreto $t$ pero no tengo una idea clara de cómo demostrar tal equivalencia.

Viniendo de un fondo de CS, si quería demostrar que un problema era $NP$ -duro, intentaría demostrar una equivalencia con un conocido $NP$ -problema difícil. ¿Podría funcionar un planteamiento similar para las funciones trampilla?

En caso afirmativo, ¿existe una lista de funciones trampilla conocidas/sospechosas?