Leonid Levin
L'allievo di Kolmogorov che scoprì la NP-completezza nell'Unione Sovietica mentre Stephen Cook faceva lo stesso in Occidente, e che pose le basi della teoria delle funzioni unidirezionali.
Nato a Dnipropetrovsk nel 1948, Levin ottenne i suoi risultati sui problemi di ricerca universale all'inizio degli anni Settanta, più o meno in parallelo con l'articolo di Cook del 1971. L'editoria sovietica era lenta e politicamente imbarazzante, perciò il riconoscimento arrivò in ritardo; oggi il risultato è noto come teorema di Cook–Levin. Emigrò nel 1978 e divenne professore alla Boston University.
Due suoi contributi interessano soprattutto i crittografi. Costruì una funzione unidirezionale universale: se esiste una qualsiasi funzione unidirezionale, la sua lo è, anche se nessuno sa dimostrare né l'una né l'altra cosa. E con Oded Goldreich mostrò nel 1989 che ogni funzione unidirezionale nasconde un bit hardcore difficile da indovinare quanto la funzione è difficile da invertire, un mattone della costruzione HILL di dieci anni dopo.