¿Qué se sabe acerca de basar la función unidireccional en el supuesto

¿Hay un resultado de imposibilidad condicional o la pregunta está completamente abierta?

No podemos esperar probar un resultado de imposibilidad general, ya que si existen funciones unidireccionales (y creemos que existen), en particular se deduce que la afirmación "Si entonces existen funciones unidireccionales" es verdadera.$P \ne NP$

Sin embargo, podemos probar que ciertas técnicas de prueba son demasiado débiles para probar esa afirmación. En particular, el siguiente artículo de Akavia, Goldreich, Goldwasser y Moshkovitz demuestra que esta afirmación no puede probarse mediante ciertas reducciones de recuadro negro (condicionadas por supuestos plausibles):

http://www.wisdom.weizmann.ac.il/~oded/p_aggm.html

Si te refieres al tipo criptográfico de función unidireccional (es decir, un caso promedio difícil de invertir), entonces la respuesta de O Meir es excelente. Pero para la noción un poco más fácil de la función unidireccional en el peor de los casos , es decir, una función inyectiva que es computable en tiempo polinomial, pero donde no existe un algoritmo determinista de tiempo polinomial tal que para todos en la imagen de y de lo contrario - hay una respuesta más precisa. Es decir, las funciones unidireccionales en el peor de los casos existen si y solo si .g f ( g ( y ) ) = y y f g ( y ) = 0 P ≠ U $f$$g$$f(g(y)) = y$$y$ $f$$g(y)=0$ $\mathsf{P} \neq \mathsf{UP}$

Entonces, para las funciones unidireccionales en el peor de los casos, su pregunta esencialmente se reduce a la relación entre y . Esta relación es esencialmente amplia, y hay oráculos en ambas direcciones. Se conocen algunas relaciones para preguntas relacionadas , a saber, Valiant-Vazirani ( ) y Hemaspaandra-Naik-Ogihara-Selman ( implica derrumba), pero no conozco ninguna relación directa e incondicional que trate con y precisión.N P N P ⊆ R P P r o m i s e U P N P M V ⊆ c N P S V P H N P U $\mathsf{UP}$$\mathsf{NP}$$\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$$\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$$\mathsf{PH}$$\mathsf{NP}$$\mathsf{UP}$