Informalmente, las funciones unidireccionales se definen con respecto a los algoritmos PTIME. Son computables en tiempo polinomial pero no invertibles en tiempo polinomial de caso promedio. La existencia de tales funciones es un importante problema abierto en la informática teórica.
Estoy interesado en funciones unidireccionales (no necesariamente para aplicaciones criptográficas) definidas con respecto a diferentes límites de recursos. Dichos límites de recursos podrían ser LOGSPACE o no determinismo limitado.
¿Existe un problema candidato (natural) que sea unidireccional con respecto a los algoritmos LOGSPACE? ¿Existe un problema candidato (natural) que sea unidireccional con respecto a los algoritmos de tiempo lineal no determinista ( )?
Estoy bien con la peor dureza de invertiblidad con respecto a los límites de recursos anteriores.
fuente
Respuestas:
Dos ejemplos específicos incluyen:
Multiplicación de enteros (hay algunas sutilezas para el OWF estándar, pero si solo te importa el peor de los casos, esto es suficiente)
fuente