Leonid Levin
Kolmogorov-eleven som upptäckte NP-fullständighet i Sovjetunionen samtidigt som Stephen Cook gjorde det i väst, och som sedan lade grunden för envägsfunktionernas teori.
Levin, född 1948 i Dnipropetrovsk, arbetade fram sina resultat om universella sökproblem i början av 1970-talet, ungefär samtidigt som Cooks artikel från 1971. Sovjetisk publicering var långsam och politiskt besvärlig, så erkännandet dröjde; i dag heter satsen Cook–Levin. Han emigrerade 1978 och blev professor vid Boston University.
För kryptografin är två bidrag centrala. Han konstruerade en universell envägsfunktion: finns någon envägsfunktion alls är just hans en sådan, även om ingen kan bevisa det. Med Oded Goldreich visade han 1989 att varje envägsfunktion har en hardcore-bit som är exakt lika svår att gissa som funktionen är att invertera. Det blev en byggsten i HILL-konstruktionen tio år senare.