Russell Impagliazzo
Théoricien de la complexité à UC San Diego qui a rangé tous les univers possibles en cinq, selon la quantité de cryptographie qu'on peut y construire.
Dans A Personal View of Average-Case Complexity (1995), Impagliazzo décrit cinq mondes : Algorithmica, où P = NP ; Heuristica et Pessiland, où il existe des problèmes difficiles mais inutilisables ; Minicrypt, où les fonctions à sens unique existent mais pas la cryptographie à clé publique ; et Cryptomania, où nous croyons vivre. Personne ne sait encore lequel est le bon.
Derrière la métaphore se cachent des résultats solides. Avec Luby, il a montré en 1989 que la cryptographie requiert des fonctions à sens unique ; avec Rudich, que l'échange de clés ne s'en déduit pas par une preuve en boîte noire ; et avec Håstad, Levin et Luby (HILL), que toute fonction à sens unique donne un générateur pseudo-aléatoire.