Hay un viejo truco para escribir un algoritmo que, si P = NP, resuelve SAT en tiempo polinómico. Esencialmente, uno enumera todas las máquinas de tiempo polinomiales y las tareas múltiples sobre ellas.
¿Existe un truco análogo para las funciones unidireccionales (o incluso las funciones de trampilla unidireccionales)? Es decir, ¿podemos escribir una función que, si existen funciones unidireccionales, es necesariamente una función unidireccional?
Parece que no hay una manera fácil de imitar el truco P = NP. En ese caso, podemos reconocer rápidamente una solución cuando la obtengamos. Pero si realizo varias tareas sobre todas las funciones de tiempo polinomiales, no hay una forma obvia de reconocer una función unidireccional cuando llego a una.
Si la respuesta a la pregunta anterior es no, ¿hay algún tipo de argumento por qué no podemos hacerlo? ¿Quizás escribir una función de este tipo demostraría de alguna manera que existen funciones unidireccionales?
fuente
Respuestas:
Sí, tal función fue encontrada por el propio Levin, publicado recientemente:
La historia de las funciones unidireccionales . Problemas de transmisión de información (= Problemy Peredachi Informatsii), 39 (1): 92-103, 2003.
fuente