Leonid Levin
L'élève de Kolmogorov qui a découvert la NP-complétude en Union soviétique pendant que Stephen Cook faisait de même à l'Ouest, puis a posé les bases de la théorie des fonctions à sens unique.
Né à Dnipropetrovsk en 1948, Levin a établi ses résultats sur les problèmes de recherche universels au début des années 1970, à peu près en parallèle de l'article de Cook de 1971. L'édition soviétique était lente et politiquement délicate, et la reconnaissance a tardé ; le résultat s'appelle aujourd'hui théorème de Cook–Levin. Il a émigré en 1978 et est devenu professeur à l'université de Boston.
Deux de ses contributions comptent surtout pour les cryptographes. Il a construit une fonction à sens unique universelle : si une fonction à sens unique existe, la sienne en est une — même si personne ne sait prouver ni l'une ni l'autre moitié. Et avec Oded Goldreich, il a montré en 1989 que toute fonction à sens unique cache un bit difficile, aussi dur à deviner que la fonction l'est à inverser. Une brique de la construction HILL, dix ans plus tard.