Il existe une vieille astuce pour écrire un algorithme qui, si P = NP, résout SAT en temps polynomial. Essentiellement, on répertorie toutes les machines à temps polynomiales et les tâches multiples sur elles.
Existe-t-il une astuce analogue pour les fonctions à sens unique (ou même les fonctions de trappe à sens unique)? Autrement dit, pouvons-nous écrire une fonction qui, s'il existe des fonctions unidirectionnelles, est nécessairement une fonction unidirectionnelle?
Il ne semble pas y avoir de moyen facile d'imiter l'astuce P = NP. Dans ce cas, nous pouvons rapidement reconnaître une solution lorsque nous en obtenons une. Mais si j'effectue plusieurs tâches sur toutes les fonctions temporelles polynomiales, il n'y a aucun moyen évident de reconnaître une fonction unidirectionnelle lorsque j'y arrive.
Si la réponse à la question ci-dessus est non, y a-t-il une sorte d'argument pourquoi nous ne pouvons pas le faire? Peut-être que l'écriture d'une telle fonction prouverait en quelque sorte qu'il existe des fonctions unidirectionnelles?
la source
Réponses:
Oui, une telle fonction a été trouvée par Levin lui-même, publiée un peu récemment:
L'histoire des fonctions à sens unique . Problèmes de transmission d'informations (= Problemy Peredachi Informatsii), 39 (1): 92-103, 2003.
la source