David Madore's WebLog: Vulgarisation sur la notion d'oracle en informatique théorique

Le concept d'oracle dont il est question ici est vient de l'informatique théorique (le terme oracle apparaît dans la thèse d'Alan Turing en 1938). Je voudrais essayer d'expliquer de façon très informelle, très vague aussi malheureusement (mais, j'espère, du coup, assez grand public) ce dont il est question.

Une partie de l'informatique théorique (l'algorithmique) s'intéresse, de façon positive, à trouver des moyens de résoudre des problèmes (mathématiquement bien définis), c'est-à-dire à concevoir des algorithmes qui les résolvent : un algorithme est un programme, un plan d'opération susceptible d'être mené dans un ordinateur — mais aussi en principe par un humain particulièrement patient — qui effectue une tâche calculatoire donnée. Par exemple, la manière dont on apprend à faire des additions et des multiplications à l'école primaire sont des algorithmes, même si ce ne sont pas forcément les plus intéressants, ils ont le mérite de nous rappeler qu'un algorithme ne tourne pas forcément sur un ordinateur, on peut aussi l'exécuter à la main (ce sera juste quelques milliards de fois plus lent…) ; d'ailleurs, le mot algorithme fait référence au mathématicien persan (écrivant en langue arabe) Muḥammad ibn Mūsá al-H̱wārizmī parce qu'il a décrit toutes sortes de méthodes systématiques pour résoudre des problèmes mathématiques, qu'on peut donc légitimement qualifier d'algorithmes, et c'était plus de 1000 ans avant l'invention des ordinateurs.

(Petite digression sur le terme algorithme : il semble qu'un mélange entre l'incompréhension des journalistes face à tout ce qui est technique et l'approximation des termes utilisés dans le contexte de l'intelligence artificielle ait fait dévier le sens du mot, dans l'image qu'en a le grand public, vers une sorte de synonyme de système opaque auquel on ne comprend rien. Certainement beaucoup de programmes utilisés dans l'ingénierie informatique moderne (notamment tout ce qui relève de l'IA) comportent énormément d'heuristiques et de méthodes mal comprises, parfois même mal comprises de leurs programmeurs ou concepteurs, et dont la réponse est parfois fausse ou mal spécifiée. Mais le sens d'algorithme en algorithmique désigne au contraire un plan bien défini et bien compris qui arrive à un résultat bien spécifié.)

Mais d'autres parties de l'informatique théorique s'intéressent non pas à concevoir des algorithmes efficaces pour résoudre tel ou tel problème, mais à se pencher sur la notion même d'algorithme et les limites théoriques du concept : que peut-on faire avec un ordinateur ?

Spécifiquement, on s'intéresse alors plutôt à des résultats négatifs : plutôt que résoudre tel ou tel problème c'est-à-dire concevoir un algorithme qui le résout, on s'attache à montrer que tel ou tel problème est difficile (long et coûteux) voire impossible à résoudre par un algorithme, ou au moins, à étudier cette difficulté, à la classifier et à la jauger. Je reste délibérément vague sur ce qu'un problème peut recouvrir ici et ce que difficile veut dire, mais je peux délimiter ici trois grands domaines où ce que je veux dire s'applique, et j'en profite pour parler un peu plus longuement de chacun des trois, en gros du plus théorique vers le plus appliqué (il n'est pas nécessaire de lire tout ce que j'écris sur chacun ci-dessous pour passer à la suite, mais je cherche à donner un minimum de contexte) :

• La théorie de la calculabilité est la branche de l'informatique théorique (possiblement la plus proche des mathématiques pures, et notamment de la logique) qui étudie ce qu'on peut faire algorithmiquement avec des ressources illimitées, c'est-à-dire, en disposant d'un temps illimité et d'une mémoire illimitée. (Le mot illimité signifie ici fini mais arbitrairement grand, sans limite a priori : c'est-à-dire que les algorithmes en question doivent s'arrêter un jour en disant j'ai terminé, mais ils ont le droit de prendre autant de temps qu'ils veulent, tant que ce temps est fini ; idem pour la mémoire : ils ont le droit de stocker toutes les données qu'ils veulent tant que cet espace utilisé reste fini à tout moment. C'est donc la forme la plus abstraite et théorique de la question que peut-on faire avec un ordinateur ? qui est étudiée ici, et elle déborde sur des questions du type comment peut-on imaginer des types de machines fondamentalement et théoriquement plus puissantes qu'un ordinateur même si elles ne sont pas réalisables en pratique ? — mentionnons par exemple que même un ordinateur quantique, qui si on réussissait à en construire serait pour certains types de problèmes incroyablement plus efficace qu'un ordinateur tel que nous disposons actuellement, ne représente pas un saut qualitatif tel qu'il peut intéresser la calculabilité : pour la calculabilité, un ordinateur quantique, un ordinateur classique, un système d'engrenages mécaniques ou encore un humain extrêmement patient et systématique muni d'un stylo et d'un papier et exécutant mécaniquement des opérations prédéfinies valent exactement la même chose.)

  La calculabilité est un peu la mère de l'informatique, parce que c'est au travers de la recherche d'une formalisation de ce qu'est un algorithme, et ce qu'un algorithme peut faire, qu'Alonzo Church et son étudiant Alan Turing sont arrivés au concept de calculabilité ; la définition précise d'algorithme à laquelle Turing est arrivé, la machine de Turing, est considéré comme une préfiguration théorique de ce qu'est un ordinateur.

  Un des thèmes majeurs de la calculabilité, donc, c'est de montrer que, pour des raisons théoriques, certains types de problèmes (mathématiquement bien posés) ne sont pas résolubles algorithmiquement : même avec un temps illimité(-mais-fini) à votre disposition, et autant de mémoire, vous ne pourrez pas écrire un algorithme qui répond à coup sûr à certaines questions qui admettent pourtant une réponse bien définie.

  L'exemple archétypal à ce sujet est le problème de l'arrêt : très grossièrement, ce problème demande justement, donné un algorithme, i.e., une suite d'instructions à exécuter (qui peut, bien sûr, contenir des boucles, du type répéter les instructions suivantes tant qu'une certaine condition n'est pas vérifiée), et des valeurs à fournir en entrée à cet algorithme, si l'algorithme en question finit (i.e., si le calcul aboutit à un résultat). Le théorème majeur de Turing, qui est à la base de la théorie de la calculabilité (et donc, dans un certain sens, de l'informatique ; mais à l'origine il s'y intéressait pour des raisons liées à la logique mathématique et spécifiquement au théorème de Gödel), c'est qu'aucun algorithme ne peut résoudre le problème de l'arrêt : autrement dit, aucun algorithme ne peut dire à coup sûr si un autre algorithme s'arrête au bout d'un temps fini. (La seule façon de savoir est de l'exécuter, ce qu'on peut faire, mais quand on l'exécute, tant qu'il n'est pas fini, on n'est jamais sûr si le programme finira par terminer plus tard.) La raison de cette impossibilité est d'ailleurs étonnamment bête une fois qu'on a fait le travail de formalisation pour rendre rigoureuse la théorie : en gros, si un algorithme existait qui puisse dire à coup sûr si un algorithme donné s'arrête, on pourrait faire un algorithme qui l'interroge et fait le contraire de ce qu'il a prédit, ce qui le met en défaut. (C'est ce qu'on appelle un argument diagonal de Cantor.)

  La calculabilité ne se contente pas, en fait, de définir des problèmes résolubles ou non résolubles algorithmiquement, et de le montrer : il y a des problèmes plus ou moins impossibles à résoudre, et l'étude des degrés d'impossibilité (par exemple les degrés de Turing dont je dirai un mot plus bas, et que je définirai précisément dans le volet technique de ce billet) est un sujet de recherche qui court depuis Turing, mais l'outil de base pour ne serait-ce que formuler ce genre de questions est la notion d'oracle que je vais chercher à introduire ici.

• La théorie de la complexité [algorithmique], cherche à être plus fine que la calculabilité : alors que la calculabilité donne aux algorithmes l'accès à des ressources (temps, mémoire) illimitées-mais-finies, la complexité s'intéresse à des problèmes résolubles par un algorithme, mais cherche à mesurer combien de temps ou de mémoire (ou parfois d'autres ressources) un algorithme devra utiliser, en fonction de la taille du problème qu'on leur pose, lorsque cette taille devient très grande. (Par exemple, combien d'étapes faut-il pour multiplier deux nombres de 100 chiffres ? de 1000 chiffres ? de 10 000 chiffres ? Avec l'algorithme qu'on apprend à l'école primaire, la réponse est en gros 10 000, 1 000 000 et 100 000 000 respectivement, parce qu'il faut multiplier chaque chiffre du multiplicande par chaque chiffre du multiplicateur avant d'ajouter tout ça : en complexité on appelle ça un algorithme quadratique. En fait, on peut faire beaucoup plus efficacement, et d'ailleurs au moins un algorithme de multiplication plus efficace sur les grands nombres que l'algorithme appris à l'école primaire peut vraiment servir à la main — enfin, pourrait servir à la main si on était dans un monde où nous n'avions pas un ordinateur en permanence avec nous.)

  La complexité est donc une discipline un peu plus applicable au monde réel que la calculabilité : alors que la calculabilité va nous donner des réponses du type vous ne pouvez pas résoudre ce problème avec un ordinateur, quel que soit le temps que vous soyez prêt à attendre ou oui vous pouvez, mais je n'ai aucune idée du temps nécessaire parce que ce n'est pas mon sujet, la complexité va chercher à voir plus précisément dans la deuxième catégorie entre des problèmes théoriquement-résolubles-mais-absolument-pas-en-pratique (un peu comme si vous cherchiez à multiplier à la main deux nombres de 1 000 000 000 000 chiffres… oui, en principe c'est possible) et des problèmes un peu plus abordables en pratique. (La complexité va aussi faire la différence entre différents types d'ordinateurs qui, pour la calculabilité sont équivalents, par exemple un ordinateur quantique permet plus de choses du point de vue de la complexité parce qu'il peut en quelque sorte mener plein de calculs en parallèle ; alors qu'en calculabilité il ne change rien du tout par rapport à un ordinateur classique.)

  Néanmoins, la complexité reste une discipline assez théorique parce qu'elle se penche sur le temps (ou la mémoire, ou une autre ressource) utilisés asymptotiquement : ici, asymptotiquement veut dire quand la taille de l'entrée de notre problème (i.e. l'instance précise) devient extrêmement grande (tend vers l'infini). C'est-à-dire que le but de la complexité n'est pas de savoir si vous allez prendre exactement tel ou tel temps pour multiplier deux grands entiers (disons) mais comment ce temps grandit quand les entiers deviennent très grands (est-ce que doubler la taille des nombres double le temps qu'il faut pour faire la multiplication ? plus ? moins ?). Tout simplement parce que c'est un peu plus abordable comme type de question (et que c'est déjà utile dans la pratique).

  La complexité définit toutes sortes de catégories de problèmes en fonction de la difficulté à les résoudre, mesurée sous la forme des ressources qu'on accepte d'allouer à un algorithme qui les résout. (Par exemple, de façon approximative, un problème est dit EXPTIME ou EXPSPACE s'il existe un algorithme qui le résout et dont le temps d'exécution ou respectivement la mémoire utilisée croît au plus exponentiellement dans la taille de la donnée ; on peut faire énormément de choses avec un temps ou une mémoire exponentielle, donc énormément de problèmes sont dans ces classes, qui ne sont pas d'un grand intérêt pratique, mais c'est quand même plus restrictif que les problèmes tout simplement calculables en ressource illimitées que j'ai évoqués plus haut.)

  Deux classes particulièrement importantes en calculabilité sont les classes P et NP. La classe P est très grossièrement celle des problèmes faciles (un peu plus précisément, ce sont ceux qui sont résolubles par un algorithme qui utilise un temps au plus polynomial dans la taille de l'entrée : linéaire, quadratique, cubique, quelque chose comme ça, mais exponentiel n'est pas permis) ; la classe NP est plus subtile : très grossièrement, ce sont les problèmes faciles à vérifier (mais pas forcément faciles à résoudre ; c'est-à-dire que si vous avez la réponse, la vérification qu'elle est correcte se fait essentiellement selon la classe P, mais par contre, si vous ne connaissez pas la réponse, il est possible qu'elle soit très difficile à trouver ; j'insiste sur le fait que mes explications sont très grossières et que je passe sur plein de subtilités théoriques).

  Un exemple de problème NP très simple à décrire est le suivant : je vous donne un tas de nombres (entiers positifs, disons) et un nombre-cible, et votre but est d'exprimer le nombre-cible comme somme de certains des nombres donnés. (C'est une variante très simple des « chiffres et les lettres » où on n'a le droit qu'à l'addition ! Ou bien imaginez que ce sont des pièces de monnaie dans un système monétaire bizarre, et vous voulez réussir à payer exactement un certain montant cible en ayant dans votre poche des pièces de certains montants donnés. Par exemple, si je vous donne les nombres 1, 3, 8, 17, 32, 51, 82, 127, 216, 329, 611, 956 et 1849, et que je vous demande de faire la somme 2146 avec, ce n'est pas évident d'y arriver sauf à tester énormément de combinaisons ; par contre, vérifier que 1 + 8 + 32 + 82 + 127 + 329 + 611 + 956 = 2146 est un calcul facile.)

  Parmi les classes que j'ai pas-vraiment-définies-mais-un-peu-évoquées, on a P ⊆ NP ⊆ EXPTIME, le symbole ‘⊆’ signifiant ici est inclus dans, c'est-à-dire que tout problème P (facile à résoudre) est en particulier NP (facile à vérifier), et que tout problème NP est lui-même, en particulier, EXPTIME (résoluble en temps exponentiel). (Ce dernier est à son tour inclus dans EXPSPACE mais peu importe.) On sait par ailleurs montrer qu'il existe des problèmes qui sont dans EXPTIME mais qui ne sont pas dans P (et on sait en décrire explicitement), autrement dit, des problèmes résolubles en temps exponentiels mais pas faciles pour autant (pas résolubles en temps polynomial) : ce n'est pas très surprenant, parce qu'une exponentielle grandit vraiment très vite, donc il n'est pas surprenant que certains problèmes puissent se résoudre en un temps exponentiel mais pas en un temps beaucoup plus limité, mais encore fallait-il le prouver (ce n'est pas très difficile, mais ce n'est pas complètement évident non plus). Bref, si voit P ⊆ NP ⊆ EXPTIME comme trois boîtes imbriquées, la plus à gauche est effectivement strictement plus petite que la plus à droite. Mais la question se pose de savoir comment est celle du milieu. En fait, on ne sait pas la situer ni par rapport à celle de gauche ni par rapport à celle de droite.

  Spécifiquement, une question centrale de la théorie de la complexité est de savoir si P=NP (en gros, est-ce que tout problème facile à vérifier est, en fait, facile à résoudre ?). On pense très fortement que la réponse est non (i.e., qu'il existe des problèmes qui sont dans NP et qui ne sont pas dans P ; on en a même plein de candidats, d'ailleurs celui que j'ai donné plus haut en est un), mais on ne sait pas le prouver (l'enjeu, ici, est de prouver rigoureusement qu'un problème est difficile au sens où il ne peut pas exister d'algorithme qui le résout facilement). Cette question P≟NP est même mise à prix à 1 000 000 $ (et attire régulièrement des « solutions » incorrectes de toutes parts).

  Pour en savoir plus sur la situation en complexité, cet article récent de vulgarisation (costaud !) dans le magazine Quanta, quoique long, n'est pas mauvais pour donner un aperçu, et expliquer un peu mieux que ce que je l'ai fait ce que c'est que cette histoire de P≟NP, ce qu'on sait dire à son sujet et quelle est la difficulté. Ce n'est pas vraiment mon propos ici d'en dire plus ici.

• La cryptographie (enfin, peut-être que je devrais plutôt dire cryptologie ici) est l'étude scientifique de la sécurité de l'information : il s'agit de développer des techniques de chiffrement (comment transformer un message en un chiffré qui ne puisse être déchiffré qu'en ayant accès à une clé) ou ayant trait à d'autres questions de sécurité de l'information (signature électronique, authenticité, non-répudiation, partage de secrets, ce genre de choses). Mais plus précisément, ici, au sein de la cryptographie, j'ai à l'esprit la cryptographie à clés publiques (voir ce billet récent pour une explication de ce que ça signifie ; ce n'est pas très important ici).

  Une différence importante entre la calculabilité/complexité et la cryptographie est qu'en cryptographie il y a un adversaire (par exemple, s'agissant d'un chiffrement, l'adversaire est un attaquant hypothétique qui essaie d'obtenir des informations sur le message sans avoir la clé de déchiffrement, ou peut-être sur la clé en ayant connaissance du message et du chiffré, ou des variantes autour de ces questions). En calculabilité ou en complexité on s'intéresse à la difficulté de problèmes parce que ça mettra une borne sur ce que nous pourrons faire. En cryptographie, on s'intéresse à la difficulté plutôt parce que ça peut représenter un travail pour l'attaquant (donc la difficulté est souhaitable !). Spécifiquement, on voudrait concevoir des méthodes de chiffrement qui soient faciles à utiliser (c'est-à-dire, peu coûteuses algorithmiquement) quand on connaît la clé, mais extrêmement difficiles à casser, c'est-à-dire pour l'attaquant qui ne connaît pas la clé, et si possible, on voudrait prouver cette difficulté, ou au moins avoir des raisons un peu plus tangibles que je ne sais pas faire, donc c'est sans doute compliqué.

Bref, dans ces trois domaines (et il y en a sans doute d'autres dont j'ignore tout ou qui ne me viennent pas à l'esprit), pour des raisons un peu différentes et avec des notions de problème et de difficulté différentes, on peut chercher à montrer qu'un certain problème est difficile (voire, s'agissant de la calculabilité, impossible, mais je vais ranger ça sous l'étiquette vague difficile), ou étudier sa difficulté.

Bon, mais comment montre-t-on qu'un problème est difficile ?

Souvent, c'est aussi très difficile. Il y a quantité de problèmes qu'on soupçonne fortement d'être très difficiles (qu'il s'agisse au sens de la calculabilité, de la complexité ou de la cryptographie, ou d'un autre sens), qui le sont assurément en pratique, mais dont on ne sait pas prouver qu'ils sont difficiles. Des trois domaines que j'ai évoqués ci-dessus (calculabilité, complexité et cryptographie), la situation est de plus en plus défavorable dans l'ordre que je viens de dire. En calculabilité, il y a plein de problèmes dont on sait prouver qu'ils sont difficiles (c'est-à-dire, dans ce contexte, pas résolubles du tout), le problème archétypal à ce sujet étant le « problème de l'arrêt » que j'ai évoqué, et les autres se « ramènent » souvent à lui au sens que je vais tenter d'expliquer plus bas. En complexité, on ne sait prouver rigoureusement la difficulté que de problèmes vraiment ridiculement difficiles (par exemple les problèmes qu'on construit pour être dans EXPTIME mais pas dans P), et toutes les questions un peu fines, notamment celle emblématique de P≟NP, demeurent ouvertes ; en cryptographie, je crois que personne n'a vraiment d'espoir d'arriver à des preuves absolues de difficulté (il n'est même pas très clair comment on devrait formellement énoncer la question, d'ailleurs).

Il y a néanmoins une idée extrêmement féconde dans les trois domaines que j'ai évoqués (calculabilité, complexité, cryptographie) qui permet de contourner de contourner un certain nombre de questions auxquelles on ne sait pas répondre (et aussi d'en ouvrir d'autres !), c'est la notion de réduction ou de difficulté relative. Je vais dire dans un instant au moins grossièrement de quoi il s'agit (et de toute façon il y a plein de variations autour de ce thème), mais c'est une façon de formaliser l'idée qu'un problème Q est « au moins aussi difficile » qu'un problème P en montrant que si on me fournit un moyen de résoudre le problème Q alors je peux m'en servir pour résoudre facilement le problème P. Et comme il s'agit cette fois d'un résultat positif, on arrive beaucoup plus facilement à obtenir de tels résultats de « réduction ». Qui font au moins avancer un peu des questions de difficulté qu'on ne sait pas résoudre de façon « absolue ».

Par exemple :

• En calculabilité, une fois qu'on a établi que le problème « de l'arrêt » est indécidable (c'est-à-dire, n'est pas résoluble par un algorithme quelconque en temps fini-mais-illimité), on se sert de réductions pour montrer qu'énormément de problèmes sont eux aussi indécidables : le schéma de raisonnement est à chaque fois si je savais résoudre le problème Q, en faisant de <telle façon> je pourrais m'en servir pour résoudre le problème de l'arrêt, or celui-ci n'est pas résoluble, donc le problème Q ne l'est pas non plus.
• En complexité, on appelle NP-dur un problème dont la résolution permet de résoudre facilement tout problème NP (peu importe exactement ce que c'est : seule importe l'approche générale). On ne sait pas montrer que ces problèmes NP-durs sont effectivement difficiles dans l'absolu (c'est, en gros, la question à 1 000 000 $ de savoir si P≟NP), mais ceci donne un indice : si un problème NP-dur quelconque était facile, alors tout problème NP serait facile (P=NP), ce qui serait très surprenant ; en tout état de cause, montrer qu'un problème est NP-dur est souvent le mieux qu'on sache faire pour expliquer qu'il est difficile : ceci donne un fort indice, et on sait qu'on ne pourra pas aller plus loin sans trancher un problème ouvert célèbre.
• En cryptographie, on ne sait jamais prouver la sécurité absolue d'un système de chiffrement ou signature (note en petits caractères : sauf quand elle l'est pour des raisons de théorie de l'information, comme le masque jetable). Ce qu'on appelle preuve de sécurité est toujours une preuve de difficulté relative, c'est-à-dire une réduction à un problème postulé difficile (la factorisation des entiers, le problème du log discret, le problème de Diffie-Hellman ou sa variante décisionnelle — peu importe ce que ce sont exactement). C'est-à-dire que l'approche par réduction est la suivante : je montre que si quelqu'un sait casser le cryptosystème étudié (là aussi, il y a plein de variantes sur ce que casser veut dire, avec des noms de code du style IND-CCA2), alors on peut s'en servir pour résoudre tel problème standard réputé difficile ; et comme implicitement on admet que le problème en question est effectivement très difficile dans l'absolu (même si on ne sait pas le prouver), ceci suggère que le cryptosystème est effectivement très difficile à casser : comme on n'a guère d'espoir d'avoir des preuves de sécurité « absolues », ces preuves par réduction sont un peu le mieux qu'on peut espérer. (Si vous voulez en savoir plus sur le sujet, je renvoie par exemple à ces slides introductives par Damien Vergnaud.)

Je passe sur énormément de détails. La manière de faire les réductions n'est pas tout à fait la même, la terminologie n'est pas tout à fait la même (c'est d'ailleurs un peu agaçant), mais dans les trois cas l'approche est globalement la même : ayant accès à un problème P que je crois difficile (dans mon premier exemple je sais même le prouver dans l'absolu), pour argumenter qu'un problème Q est difficile, je montre que si je sais résoudre Q je peux m'en servir pour résoudre facilement P.

Bon, mais qu'est-ce que ça veut dire qu'on peut réduire (ou ramener) le problème P au problème Q ? Et quel rapport avec le mot oracle ?

Il y a toutes sortes de petites variations autour de la définition (et le but du billet technique qui est censé suivre sera de décrire certaines de ces variations), mais l'idée générale très grossière est que :

Le problème P est réductible (ou ramenable) au problème Q quand, si on me fournit un moyen magique pour résoudre le problème Q, je peux utiliser ce moyen pour résoudre (« facilement ») le problème P.

Ce moyen magique hypothétisé s'appelle un oracle.

Voici un exemple complètement stupide mais qui illustre peut-être ce que je veux dire : le problème de trouver l'âge du capitaine est réductible au problème de trouver l'état-civil précis du capitaine, parce que si je trouve l'état-civil précis du capitaine, il y a sa date de naissance dedans, et je peux facilement en déduire son âge. (Donc, si on me donne un oracle qui est capable de me fournir l'état-civil du capitaine d'un bateau alors cet oracle me permet de donner l'âge du capitaine.) Et indiscutablement, ceci est une façon d'expliquer qu'il est au moins aussi difficile de trouver l'état-civil précis du capitaine que de trouver son âge. Les réductions utilisées en informatique théorique sont rarement aussi triviales (encore que parfois elles le sont), et les problèmes dont on parle sont des problèmes mathématiquement bien définis (et paramétriques, c'est-à-dire qu'il y a une entrée au problème — ici ça pourrait être le bateau dont on demande l'âge du capitaine), mais l'idée est là. Il me semble que même dans la vie courante on fait occasionnellement appel à ce genre de raisonnements : tu te doutes bien que je ne peux pas faire Q, sinon je pourrais aussi faire P et je le ferais.

Ce qu'on appelle un oracle, c'est donc un objet théorique (une boîte noire, c'est-à-dire qu'on ne se préoccupe pas de comment elle fonctionnerait à l'intérieur : « c'est magique ») qui, quand on lui demande la réponse à un certain problème (Q dans ma notation ci-dessus), la fournit immédiatement et parfaitement. Et on s'interroge sur ce qu'on peut faire, ensuite, donné un tel oracle.

Mais si c'est l'idée approximative, que j'ai décrite ici de façon délibérément vague, il existe toutes sortes de variations autour de cette idée. Déjà, en cryptographie, la terminologie est un peu différente : le terme d'oracle est le plus souvent utilisé spécifiquement dans l'expression spécifique oracle aléatoire, c'est-à-dire que l'oracle répond aléatoirement (si on veut, il tire un dé parfait à chaque fois qu'on l'interroge, à ceci près que le tirage est enregistré en face de la question qu'on lui a posée, et que toute répétition de la même question conduira à la même réponse), ce qui ne semble pas très utile, et de fait ça ne l'est pas (et c'est assez indépendant de la question de réduire un problème P à un problème Q), mais c'est une façon de contourner le fait qu'un ordinateur idéalisé ne possède pas de source de vrai aléa (les primitives cryptographiques comme des fonctions de hachage sont des imitations en plastique d'un oracle aléatoire) ; néanmoins, la notion de réduction que j'ai évoquée ci-dessus est quand même largement utilisée en cryptographie.

Questions de terminologie mises à part, le premier intérêt de la notion d'oracle, c'est pour définir la notion de réduction que j'ai discutée ci-dessus : on dit qu'un problème P est calculable, ou facile, ou je ne sais quoi, relativement au problème Q, lorsqu'une machine doté d'un oracle répondant à Q peut, ou peut facilement, ou quelque chose comme ça, répondre au problème P : c'est là la notion de réductibilité définie plus haut.

Si on sait (« facilement ») résoudre le problème P en disposant d'un oracle qui résout le problème Q, cette « réduction » montre que le problème Q est au moins aussi difficile que le problème P, et comme je l'ai dit cette démarche est utile en calculabilité (pour montrer que certains problèmes ne sont pas résolubles, en y réduisant un problème connu pour ne pas l'être, par exemple le problème de l'arrêt), en complexité (faute de savoir montrer que certains problèmes NP sont vraiment durs dans l'absolu, on peut au moins montrer que tout problème NP se ramène à eux) et en cryptographie (comme argument tendant à établir la sécurité d'un chiffrement).

Mais une fois qu'on a dégagé cette notion de difficulté relative, et de calcul avec oracle, on peut bien sûr l'étudier plus loin et pour elle-même : que peut-on faire avec tel ou tel oracle ?

C'est-à-dire qu'on peut se pencher sur la puissance de ce nouveau type de dispositif de calcul : un ordinateur (enfin, une machine de Turing, c'est-à-dire un ordinateur idéalisé) disposant d'un oracle résolvant tel ou tel problème fixé. C'est une généralisation de la notion de machine sans oracle, parce qu'une machine sans oracle est essentiellement la meme chose qu'une machine avec un oracle qui fournit des réponses sans intérêt (par exemple, qui ne répond rien, ou qui répond toujours 0, quand on l'interroge). Du coup, on peut aussi reprendre plein de questions qu'on se posait sur les machines de Turing sans oracle et s'interroger sur la même question pour les machines de Turing disposant d'un oracle répondant à tel ou tel problème (soit pour un problème précis, soit n'importe quel oracle, soit des catégories générales). Ça s'appelle relativiser la question.

L'enjeu est alors un petit peu différent. Les oracles considérés ne résolvent plus forcément un problème utile : on se pose plutôt des questions du type si je donne à un ordinateur accès à un oracle qui calcule telle fonction f, que peut-il en faire ? (peut-être que la fonction f est faite exprès pour qu'il se passe des choses bizarres, ou peut-être qu'on cherche à démontrer des choses pour toute fonction f ou quelque chose comme ça).

À titre d'exemple, en complexité, j'ai dit qu'on ne savait pas répondre à la question P≟NP (en gros est-ce que tout problème vérifiable facilement est résoluble facilement ? — on pense bien sûr que la réponse est non, ce serait trop beau, mais on ne sait pas le prouver) ; mais cette question concerne les ordinateurs usuels, sans oracle : on peut reposer exactement la même question en donnant à l'ordinateur accès à un oracle (résolvant tel ou tel problème ou telle ou telle catégorie de problèmes) : on peut montrer que pour certains types d'oracles (fabriqués exprès), P=NP devient vrai, et pour certains on a au contraire P≠NP : ceci ne nous donne pas la réponse à ce qui se passe sans oracle, mais ceci donne un indice expliquant pourquoi la question P≟NP est difficile : une réponse ne peut pas venir d'un argument très général, elle doit forcément faire appel aux particularités du modèle de calcul.

En calculabilité (où, de façon générale, on sait dire beaucoup plus de choses qu'en complexité), la notion de machines avec oracle donne naissance à la théorie des degrés de Turing : on dit que deux problèmes sont dans le même degré de Turing lorsqu'on peut réduire chacun des deux à l'autre, c'est-à-dire qu'on peut calculer la réponse à chacun des deux si on dispose d'un oracle qui répond à l'autre : c'est une façon de dire que les deux problèmes ont la même difficulté calculatoire (mais au sens de la calculabilité, c'est-à-dire sans aucune limite sur les ressources disponibles : disons peut-être plutôt la même impossibilité calculatoire). La notion de réduction définit un ordre sur les degrés de Turing : dire que le problème P se réduit au problème Q (i.e., est résoluble avec lui pour oracle) peut aussi se dire sous la forme que le degré de Turing de P est inférieur ou égal à celui de Q (i.e., est plus facile au sens large). L'étude des degrés de la structure des degrés de Turing et de leur ordre est un sujet important : si tout ce qui est calculable constitue un degré de Turing noté 0 (le plus petit) et le problème « de l'arrêt » en définit un autre noté 0′, ceci ouvre la voie à plein d'autres questions et à une vaste théorie. Par exemple : existe-t-il des degrés entre 0 et 0′ ? (c'est-à-dire des problèmes insolubles algorithmiquement mais auxquels on ne puisse pas non plus ramener le problème de l'arrêt — la réponse est oui, mais il y a des variantes autour de cette question qui sont très subtiles). On peut aussi définir le problème de l'arrêt sur les machines à oracle : pour tout degré de Turing d ceci définit un nouveau degré de Turing d′, strictement plus grand, qui correspond au problème de l'arrêt pour les machines disposant d'un oracle du degré d. Notamment, le problème de l'arrêt pour les machines ayant elles-mêmes accès à un oracle pour le problème de l'arrêt appartient au degré 0′′, et on peut chercher à répéter la manœuvre de façon transfinie (là aussi il y a des questions subtiles).

En cherchant à donner juste un aperçu (sans vraies définitions, et juste en agitant les mains) de certaines des questions qu'on peut se poser en théorie de la calculabilité et de la complexité, j'ai évidemment énormément simplifié et parfois dit des choses un peu fausses. Par exemple, j'ai agité les mains en utilisant le terme excessivement vague de problème, mais il aurait au moins fallu distinguer les problèmes de décision (ceux dont la réponse est oui ou non) des autres.

Je dois aussi signaler qu'il y a beaucoup de variations autour de la notion de réduction. J'ai laissé comprendre (enfin, j'espère qu'on l'aura compris) qu'elle est différente en calculabilité, où on dit que P est réductible à Q quand, donné un oracle qui répond à Q, je peux utiliser ce moyen pour résoudre le problème P algorithmiquement (en temps fini-mais-illimité), et en complexité, où on exige en plus que l'algorithme ne prenne pas trop de temps ou de mémoire (typiquement, qu'il soit de complexité P relative à l'oracle fourni). Mais il y a un autre type de distinction qui peut jouer, et qui vaut la peine d'être mentionné :

• dans la réduction de Turing, que j'avais implicitement à l'esprit en écrivant l'essentiel de ce qui précède, l'oracle fourni est interrogeable ad libitum, c'est-à-dire qu'il n'y a pas de limite sur son nombre d'utilisations (l'algorithme qui l'utilise a le droit de l'interroger autant de fois qu'il le souhaite ; bien sûr, si on parle de théorie de la complexité, il y a un coût en temps associé à cette interrogation, mais il n'est pas plus élevé que n'importe quelle opération normale de l'algorithme) ;
• dans la réduction de Weihrauch [le terme n'est pas complètement habituel, parce qu'il sert plutôt dans un contexte un peu différent, mais je n'en connais pas de meilleur], l'oracle ne peut servir qu'une seule fois, i.e., il n'acceptera de répondre qu'à une seule question (et du coup, évidemment, on peut s'interroger sur la réduction de Weihrauch à 2, 3, 4… copies du même oracle, pour autoriser de poser 2, 3, 4… questions) ;
• dans la réduction many-to-one (ou réduction applicative, je ne connais pas vraiment le terme français, s'il y en a), non seulement l'oracle ne répond qu'à une seule question mais en plus son interrogation est terminale, c'est-à-dire que la réponse de l'oracle à la question qu'on lui pose doit nécessairement fournir la réponse au problème posé initialement, on n'a pas le droit de la modifier derrière ni de travailler dessus (i.e., on dit que P est réductible many-to-one à Q lorsqu'il existe un algorithme qui, donnée une instance du problème P, fournit une instance du problème Q qui ait exactement la même réponse).

(Il y a même la réduction one-to-one qui est encore plus restrictive en ce sens que les questions posées à l'oracle pour différentes instances du problème doivent être distinctes, mais elle ne me semble pas très intéressante.)

Ces notions existent à la fois en calculabilité et en complexité, même si en complexité on utilise parfois une terminologie gratuitement différente (réduction de Cook pour la réduction de Turing en temps P et réduction de Karp pour la réduction many-to-one en temps P ; je ne sais pas pourquoi la réduction de Weihrauch n'est pas plus populaire alors qu'elle semble quand même très naturelle dès qu'on n'a pas affaire à un problème de décision).

On peut aussi évoquer différentes variations autour de l'oracle lui-même, et pas tellement sur son mode d'interrogation. Par exemple, certains types d'oracles peuvent avoir des « questions interdites » (si vous la posez, l'oracle explose et vous mourez, mais ça peut être un problème lui-même difficile de savoir quelles questions sont interdites) : on parle ici d'oracles partiellement définis ; certains types d'oracles peuvent avoir plusieurs réponses possibles pour une question (et ils vont chercher à vous embêter en vous fournissant celle qui vous arrange le moins, ou au moins toute stratégie pour s'en servir doit tenir compte de cette possibilité) : on parle ici d'oracles non-déterministes. Un oracle peut éventuellement renvoyer une information sur une infinité de questions à la fois : j'avais notamment évoqué autrefois la notion de machine hyperarithmétique qu'on peut voir comme une machine disposant d'une sorte d'oracle permettant de tester une infinité de valeurs d'une fonction (la fonction étant elle-même définie par une machine hyperarithmétique, donc il faut être soigneux dans la définition) : le terme technique ici est calculabilité dans une fonctionnelle de type 2 (de type 2 parce qu'on peut aller encore plus loin).

Je ne vais pas plus loin, mon but dans ce billet étant juste d'expliquer comment cette notion d'oracle ouvre la porte à plein de questions théoriques, et je vais m'arrêter là. Mais auparavant, voici une petite énigme que je trouve amusante et intéressante, et qui a un rapport avec une certaine notion d'oracle (et notamment celle que je dois expliquer dans le deuxième volet) :

Vous êtes dans un donjon face à cinq (5) portes identiques. Deux (2) d'entre elles (au maximum) conduisent à la mort, et les autres conduisent au trésor que vous convoitez. Vous ne savez pas lesquelles. Votre but est d'ouvrir une porte au trésor.

Vous avez heureusement la possibilité d'interroger un petit lutin (plus exactement, l'Omniscient Rouspéteur Aventurier Coquin Lutin Extraordinaire) qui connaît les bonnes portes. Mais ce petit lutin n'accepte de répondre aux questions que sous une forme très particulière : pour l'interroger il faut lui dire trois (3) phrases dont au maximum une (1) est fausse : le lutin répond alors en vous disant une phrase vraie parmi celles que vous lui avez proposées. Si on enfreint la règle (en proposant au lutin des phrases dont >1 soit fausse), alors il vous tue et vous mourez, de même que si vous ouvrez une mauvaise porte.

En revanche, vous avez le droit d'interroger le lutin autant de fois que vous voulez. Mais il cherche à vous embêter en vous fournissant les réponses les moins utiles possibles (ou du moins, il faut se préparer à cette possibilité ; par exemple si on lui propose les trois phrases la première porte est mortelle, la première porte n'est pas mortelle et 2+2=4, ce qui vérifie effectivement la contrainte exigée, il va vous répondre que 2+2=4 est vrai).

Comment faire pour identifier à coup sûr une porte non-mortelle ?

En tant que tel, ce problème n'est pas forcément terriblement intéressant (je ne sais pas dire à quel point il est difficile), mais on peut s'interroger sur la question plus générale : si on remplace 5, 2, 3, 1 dans l'énigme par respectivement k, m, k′, m′ (avec 0<k<m et 0<k′<m′), à quelle condition peut-on obtenir la réponse à coup sûr ? Et quelle est la bonne façon de formuler le problème ? À quel type d'oracle ceci correspond-il, et peut-on en donner des exemples différents de la même nature ? Je donnerai une réponse dans la suite prévue à ce billet, mais je demeure perplexe quant à savoir quel est le bon cadre théorique pour étudier ce genre de problèmes.