Imaginez que vous cherchez à comprendre la nature même du calcul. Vous êtes au cœur du désert, loin de tout chemin, et impénétrable messages sont gravés dans les troncs d'arbres tout autour de vous - BPP, AC⁰[m], Σ₂P, YACC et des centaines d'autres. Les glyphes essaient de vous dire quelque chose, mais par où commencer ? Vous ne pouvez même pas les garder tous droits.

Peu de chercheurs ont fait autant Russel Impagliazzo pour briser ce chaos apparent. Depuis 40 ans, Impagliazzo a travaillé à l'avant-garde de la théorie de la complexité computationnelle, l'étude de la difficulté intrinsèque de différents problèmes. La question ouverte la plus célèbre dans ce domaine, appelée le problème P versus NP, demande si de nombreux problèmes informatiques apparemment difficiles sont en réalité faciles – avec le bon algorithme. Une réponse aurait des implications considérables pour la science et la sécurité de la cryptographie moderne.

Dans les années 1980 et 1990, Impagliazzo a joué un rôle de premier plan dans l'unification du fondements théoriques de la cryptographie. En 1995, il a articulé l'importance de ces nouveaux développements dans un article emblématique qui reformulait les solutions possibles à l'opposition P versus NP et une poignée de problèmes connexes dans le langage de cinq mondes hypothétiques nous pourrions habiter, surnommés de manière fantaisiste Algorithmica, Heuristica, Pessiland, Minicrypt et Cryptomania. Les cinq mondes d'Impagliazzo ont inspiré une génération de chercheurs et continuent de guider la recherche dans le sous-domaine florissant de méta-complexité.

Et ce ne sont pas les seuls mondes qu’il a imaginés. Impagliazzo est un passionné depuis toujours de jeux de rôle sur table comme Donjons et Dragons, et il aime inventer de nouveaux ensembles de règles et de nouveaux paramètres à explorer. Le même esprit ludique anime sa pratique de la comédie improvisée depuis 30 ans.

Impagliazzo a également réalisé un travail fondamental élucidant le rôle fondamental du hasard dans le calcul. À la fin des années 1970, les informaticiens ont découvert que le hasard pouvait parfois améliorer les algorithmes pour résoudre des problèmes intrinsèquement déterministes – une découverte contre-intuitive qui a laissé les chercheurs perplexes pendant des années. Le travail d'Impagliazzo avec le théoricien de la complexité Avi Wigderson et d'autres chercheurs dans les années 1990 ont montré que si certains problèmes informatiques sont réellement fondamentalement difficiles, alors il est toujours possible pour convertir les algorithmes qui utilisent le hasard en algorithmes déterministes. Et inversement, prouver que le hasard peut être éliminé de n’importe quel algorithme prouverait également que des problèmes vraiment difficiles existent.

Quanta a parlé avec Impagliazzo de la différence entre des problèmes difficiles et des énigmes difficiles, de la consultation d'oracles et des leçons mathématiques de la comédie d'improvisation. L'interview a été condensée et éditée pour plus de clarté.

Quand avez-vous commencé à vous intéresser aux mathématiques ?

Je m’intéressais aux mathématiques avant même de savoir vraiment de quoi il s’agissait. En troisième année, mes notes en mathématiques ont commencé à baisser parce que nous étions censés mémoriser nos tables de multiplication, et j'ai refusé. Ma mère a dit : « Mais Russell, tu aimes les mathématiques, pourquoi ne fais-tu pas ça ? Et j'ai dit : « Ce ne sont pas des mathématiques, c'est de la mémorisation. Les vraies mathématiques n’impliquent pas de mémorisation. Tout ce que j’avais appris à ce moment-là était l’arithmétique, donc je ne sais pas d’où m’est venue l’idée que les mathématiques concernaient des concepts abstraits.

Qu’en est-il de l’informatique ? Certaines parties du domaine sont très abstraites, mais ce n’est pas ce que la plupart des gens découvrent en premier.

Au lycée, j'avais suivi un cours de programmation en BASIC, mais c'était vraiment difficile de faire quoi que ce soit. Les programmes devaient être transférés sur des bandes de papier, qui devaient être exécutées via ce très vieil ordinateur qui fonctionnait souvent mal et déchirait votre papier en deux. Je pensais donc que l’informatique était terriblement ennuyeuse.

J'avais l'intention d'étudier la logique. Mais beaucoup de concepts, lorsque vous avez essayé de les formaliser, impliquaient le calcul et surtout les limites du calcul. Des questions telles que « Comment savons-nous que les choses en mathématiques sont vraies ? » et "Comment comprenons-nous la difficulté de faire des mathématiques?" conduit à l'informatique théorique, et en particulier à la théorie de la complexité.

Certains de vos travaux les plus célèbres explorent les liens entre la cryptographie et la théorie de la complexité informatique. Pourquoi ces deux domaines sont-ils liés ?

Lorsque vous configurez un système cryptographique, vous devez faire la distinction entre les utilisateurs légitimes (les personnes auxquelles vous souhaitez accorder l'accès) et tous les autres. Des problèmes informatiques difficiles nous permettent de distinguer ces groupes en fonction de ce qu’ils savent. Mais si vous voulez que connaître la réponse à un problème soit un moyen de distinguer deux groupes de personnes, vous ne pouvez pas utiliser n’importe quel problème difficile : vous avez besoin d’un puzzle difficile.

Quelle est la différence entre un problème et un puzzle ?

En général, la personne qui pose un problème ne connaît peut-être pas la réponse. Un puzzle est un problème conçu avec une réponse en tête. Alors pourquoi avons-nous besoin d’un puzzle ? Parce que nous devons être capables de déterminer si la personne qui est censée l’avoir résolu l’a réellement fait. Dans la vie de tous les jours, nous utilisons des puzzles pour nous amuser, mais nous les utilisons également dans les salles de classe pour vérifier si les gens ont compris le matériel. C'est ce qui se passe en cryptographie : nous utilisons des énigmes pour tester les connaissances de quelqu'un.

La différence entre les cinq mondes réside dans la manière dont ils répondent aux questions « Y a-t-il des problèmes difficiles ? » et "Y a-t-il des énigmes difficiles ?"

Comment se manifestent ces différentes réponses ?

Dans le premier monde, Algorithmica, aucun problème n’est difficile. Vous n'avez pas besoin de savoir comment quelqu'un a conçu votre problème : vous pouvez toujours le résoudre. Heuristica dit : « Eh bien, peut-être que certains problèmes sont difficiles. » Nous arrivons ensuite au pays Pessi, où de nombreux problèmes sont difficiles, mais la plupart des énigmes ne le sont pas. Presque tous les problèmes que je crée et dont je connais la solution, vous pourrez également le résoudre. Tous ces mondes sont mauvais pour la cryptographie.

Dans Minicrypt, je peux créer des énigmes que je sais résoudre et qui restent très difficiles pour vous. Et enfin, Cryptomania est un monde dans lequel deux personnes peuvent se tenir dans un lieu public où une écoute indiscrète peut entendre et créer ensemble un puzzle qui est encore difficile pour l'oreille indiscrète.

Qu’est-ce qui vous a motivé à rédiger l’article des cinq mondes ?

À l’époque, on savait que différentes réponses à la question P versus NP auraient un impact important sur le type de problèmes que nous pourrions résoudre et également sur le type de sécurité que nous pourrions espérer, mais les distinctions qualitatives entre les différentes formes de facilité et la dureté n'était pas vraiment claire.

Quelques années plus tôt, un article très perspicace présentait les distinctions en utilisant de nombreuses questions interdépendantes avec environ 20 réponses possibles. L’une des raisons pour lesquelles j’ai voulu rédiger cet article sur les cinq mondes était que nous avions fait d’énormes progrès au cours de ces quelques années. Il aurait été difficile de trouver des noms pour 20 mondes possibles.

Alors pourquoi le présenter de cette façon, comme des mondes différents avec des noms bizarres ?

J'avais accepté d'écrire cet article pour une conférence. Je restais éveillé tard dans la nuit pour essayer de comprendre ce que j'allais dire, et vers 1 heure du matin, le cadrage des différents mondes semblait être une bonne idée. Et puis je l’ai lu le lendemain matin et cela semblait toujours être une bonne idée – c’était une façon de montrer comment ces idées allaient réellement influencer le monde sans se laisser entraîner dans des détails quantitatifs. Ce qui me rend le plus heureux dans cet article, c'est que j'entends dire par des personnes effectuant des recherches sur la complexité que c'est l'article qui les a amenés à s'intéresser au domaine en tant qu'étudiants de premier cycle.

Les chercheurs ont-ils exclu l’un des cinq mondes possibles ?

En fait, nous en ajoutons davantage – les gens ont commencé à en parler Obfustopie comme un monde d’outils cryptographiques encore plus puissants. Il est un peu déprimant que nous ayons fait autant de progrès à la fin des années 1980 et que nous n'ayons éliminé aucun monde depuis. Mais d’un autre côté, nous en savons beaucoup plus sur les connexions entre les mondes et disposons d’une image beaucoup plus claire de ce à quoi ressemblerait chaque monde.

Les mondes hypothétiques jouent également un autre rôle dans la théorie de la complexité, dans les preuves qui supposent l’existence d’« oracles ». Alors, tout d’abord, qu’est-ce qu’un oracle exactement ?

Imaginez que quelqu'un construise un appareil ingénieux capable de résoudre un problème sans que nous connaissions un algorithme permettant de résoudre ce problème. C'est ce qu'est un oracle. Si nous avions un appareil aussi miraculeux et que nous le placions dans nos ordinateurs, il pourrait déplacer la frontière entre ce qui est calculable et ce qui ne l’est pas.

Les chercheurs pensent-ils que ces boîtes magiques pourraient réellement exister ?

Non, ils n'existent probablement pas. Au début, les résultats des oracles étaient quelque peu controversés car ils étaient très hypothétiques. Mais ils peuvent être très instructifs lorsque l’oracle est utilisé pour modéliser une situation idéale. Supposons que vous essayiez de montrer que A n'implique pas nécessairement B. Vous commencez par le paramètre où vous avez le A le plus extrême et montrez que cela n'est toujours pas suffisant pour garantir B. Si vous pouvez montrer que même si toutes les chances sont en votre faveur, vous ne pouvez toujours pas prouver quelque chose, c'est une preuve très solide que cela va être difficile à prouver.

Vous avez également découvert des liens entre la dureté des calculs et le caractère aléatoire. Comment fonctionne cette connexion ?

C'est vraiment une façon de dire que si vous ne comprenez pas quelque chose, cela peut paraître aléatoire. Supposons que je dise que je pense à un nombre compris entre un et mille. Si je choisis le numéro au hasard, vous avez une chance sur mille de le deviner. Et si je demande – à la suite des Monty Python – « En miles par heure, quelle est la vitesse moyenne d'une hirondelle européenne ? vous avez à peu près la même chance. Cela va probablement à plus d'un mile à l'heure, et cela ne va probablement pas à plus de mille miles à l'heure.

Ce n’est pas vraiment aléatoire – c’est une question à laquelle il est possible de répondre de manière déterministe. Nous pourrions simplement mesurer toutes les hirondelles qui volent, mais c'est assez difficile à déterminer avec des ressources limitées, comme ne pas avoir de budget pour mesurer la vitesse des hirondelles et ne pas avoir une réserve infinie d'hirondelles.

L'idée est donc que des problèmes difficiles dont nous ne connaissons pas les solutions peuvent fournir une source de nombres « pseudo-aléatoires » qui semblent aléatoires.

En parlant de Monty Python, je sais que vous faites de la comédie d'improvisation depuis longtemps maintenant. Comment avez-vous commencé ?

J'ai commencé comme professeur adjoint à San Diego en 1991. Et vers 94 environ, je me suis dit : « Je n'ai vraiment pas beaucoup de vie en dehors du département. J'ai donc reçu l'hebdomadaire gratuit et j'ai parcouru la liste des clubs et des activités. J'ai tout éliminé sauf la comédie d'improvisation – je pensais qu'il était au moins plausible que je sois d'accord. J'ai rencontré ma femme dans ce cours pour débutants.

Qu'en a-t-elle pensé?

Elle dit que j'étais vraiment horrible. Lorsque vous êtes logicien, vous êtes formé pour toujours penser à la nuance de chaque mot. Vous ne voulez pas dire quelque chose d'incorrect. L'improvisation est géniale dans la mesure où elle inverse cela : le but n'est pas de dire quelque chose de parfait mais d'inventer quelque chose rapidement. C'était le contraire du reste de ma vie.

Mon épouse actuelle a fait une pause dans les cours et lorsqu'elle est revenue un an plus tard, j'ai réussi à l'impressionner. C'était il y a 30 ans. Je prends toujours le même cours avec le même instructeur.

L’improvisation a-t-elle changé votre façon d’aborder vos recherches ?

C'est une bonne pratique pour ne pas être hypercritique à propos de chacune de vos pensées. C’est particulièrement utile dans les collaborations. Lorsque je travaillais avec d'autres personnes, j'avais l'habitude de dire des choses comme : « Mais cette idée ne fonctionnera pas pour la raison suivante. Ce n’est pas littéralement vrai. En improvisation, vous êtes toujours censé accepter ce que dit votre partenaire. Et je pense que c'est une bonne attitude à adopter, surtout lorsque vous faites des recherches avec des étudiants : ne rejetez pas quelque chose qu'ils disent simplement parce que vous savez que c'est incorrect. Il existe de nombreuses bonnes idées qui ne sont pas correctes à 100 %.

Comme ça?

Lorsque vous essayez d’avoir une intuition sur un problème, une chose qui peut vous aider est de commencer par quelques hypothèses simplificatrices. Ces hypothèses ne sont généralement pas vraies, mais elles peuvent vous aider à élaborer une feuille de route. Dites : « Si j’avais un éléphant, je pourrais franchir les montagnes. Bien sûr, je n'ai pas d'éléphant. Mais si je le faisais, voici comment je procéderais. Et puis vous réalisez : « Eh bien, peut-être que je n'ai pas besoin d'un éléphant pour cette étape. Une mule ferait l’affaire.

Qu’en est-il de votre amour des jeux de rôle : cela a-t-il influencé votre travail ?

Cela n’a peut-être pas influencé toutes mes recherches, mais cela a certainement influencé mon article sur les cinq mondes. J'ai toujours eu un intérêt général pour la fantasy et la science-fiction et pour l'idée de différents mondes possibles : à quoi ressembleraient les choses si tout était différent ?

Pourquoi les jeux de rôle constituent-ils un moyen si convaincant d’explorer des mondes hypothétiques ?

Les amateurs de fiction spéculative ont toujours inventé des mondes. Tolkien est surtout connu pour cela, et il avait une imagination si massive que son monde semblait réellement habité. Pour ceux d'entre nous qui ne sont pas aussi imaginatifs, la meilleure façon d'y parvenir est d'inviter des gens dans votre environnement et un jeu est une façon de le faire. Maintenant, ce n'est pas seulement mon monde. Cela a peut-être commencé comme je l'imaginais, mais comme dans toute collaboration, grâce aux contributions de tous, tout a évolué bien au-delà.