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?
