¿Función que se garantiza que es unidireccional si existen funciones unidireccionales?

13

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?

Timothy Chow
fuente
Hola Timothy Chow, ¿tal vez puedas ayudar y señalar un enlace donde el truco para escribir un algoritmo, que si P = NP, resuelve SAT en tiempo polinómico, se formaliza? Muchas gracias
Avi Tal
@AviTal Vea por ejemplo esto: scholarpedia.org/article/Universal_search
Vanessa

Respuestas:

11

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.

Bjørn Kjos-Hanssen
fuente
¡Gracias! Utilizando Google Scholar, pude usar esta referencia para encontrar una referencia para un criptosistema de clave pública completo, por Grigoriev, Hirsch y Pervyshev, Groups-Complexity-Cryptology 1 (2009), 1-12.
Timothy Chow
¿Podría explicar los detalles de esta función? Como por qué aborta después de n ^ 2 pasos, por qué 'preservar una copia del prefijo del programa y forzarlo, así como la longitud de entrada, en la salida' y qué 'solo en lugares donde tal extensión posible es única' significa exactamente . No sé si esto merece una pregunta por separado.
galmeida
@ BjørnKjos-Hanssen cstheory.stackexchange.com/questions/44496/…
galmeida