Je suis daltonien, mais je m’en sors...

Piste verte 20 février 2012  - Ecrit par  Antoine Chambert-Loir Voir les commentaires

En théorie de la complexité, les preuves interactives permettent, via un jeu de questions et réponses, de certifier, avec une très forte probabilité, la véracité d’un énoncé. En voilà un exemple, où il est question des chaussettes d’un daltonien.

J’ai un problème, je suis daltonien. Enfin, pas vraiment, c’est juste que je distingue mal certaines couleurs quand elles sont un peu trop proches. Vous me direz que c’est pareil pour tout le monde. Disons alors que je distingue mal des couleurs que vous distingueriez peut-être.

Un problème de couleurs de chaussettes

Voilà ce qui m’est arrivé l’autre jour. De bon matin (pas si bon que ça, d’ailleurs, mais c’est une autre histoire), j’enfilais mes chaussettes, un peu endormi, quand ma fille de 4 ans s’exclame : « Mais ! tu n’as pas mis des chaussettes de la même couleur ! » (Ça l’a fait beaucoup rire, d’ailleurs, parce qu’elle adore jouer à ce jeu, mais là encore, c’est une autre histoire.) J’ai regardé mes pieds, et c’est là que ça s’est gâté : ben non, elles étaient de la même couleur mes chaussettes.

Ma fille se marre, appelle son grand frère, qui rigole tout autant. Quelques minutes plus tard, mes trois enfants sont là, autour de moi, à s’esclaffer devant mes chaussettes, à ce qu’ils disaient l’une bleue, l’autre grise, mais qui pour moi étaient toutes deux grises.

J’ai cru qu’ils me faisaient une blague. D’ailleurs, ils riaient si bien ! J’ai protesté, vainement, si bien qu’à un moment j’ai répondu : « OK, démontrez-moi qu’elles sont bien de couleurs différentes ! »

— Ben, a dit l’autre fille, elles sont de couleurs différentes, c’est tout.
— Peut-être, mais je ne vous crois pas. Prouvez-le moi.
— On peut aller chercher maman ?
— Non, je ne la croirai pas non plus. (Enfin, si, je l’aurais crue, mais c’est une autre histoire...)
— Ce n’est pas possible, si tu ne veux pas nous croire.

C’est là que j’ai commencé à m’amuser...

— Eh si, c’est possible, et je vais vous montrer comment.

Une solution du problème

J’ai enlevé mes chaussettes, j’ai pris l’une dans une main et l’autre dans l’autre, et
je leur ai demandé laquelle était bleue, et laquelle était grise. Puis je me suis
retourné, j’ai passé les chaussettes d’une main à l’autre un certain nombre de fois, sans leur montrer ce que je faisais, mais en me rappelant bien (ce n’était pas facile d’ailleurs...) où devait être la chaussette prétendument bleue, et où était la grise.
Puis je leur ai demandé :

— Et alors, laquelle est bleue ?

Et eux, d’une seule voix :

— C’est la droite !

Là, j’ai été bluffé : ils avaient raison ! Bien sûr, je ne savais pas si elle était bleue ou grise, puisque je ne faisais pas la différence avec celle de la main gauche, mais ce que je savais bien, c’est que j’avais changé les chaussettes de mains, et qu’au début ils m’avaient dit que la bleue était à gauche.

Je me suis dit qu’ils avaient peut-être eu de la chance (encore que, s’ils étaient tous les trois d’accord, il devait bien y avoir un fond de vérité), et j’ai recommencé l’expérience deux fois, trois fois, dix fois... Ils ne se sont jamais trompés.
Si bien que j’ai fini par les croire : si elles avaient été toutes deux identiques, comme je le croyais, comment auraient-ils pu deviner si j’avais échangé les chaussettes
ou pas ?

J’ai donc rangé mes deux chaussettes dans le placard, et j’en ai pris deux autres... avec des rayures, je n’en ai qu’une paire comme ça.

Conclusion

Est-il la peine de dire que cette histoire est inventée, comme le sont toutes les belles histoires ? C’est ma lecture du livre de Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach qui l’a suscitée.

Le chapitre 8 du livre d’Arora et Barak est consacré aux preuves interactives.
Introduites en 1985 par Goldwasser, Micali et Rackoff d’une part, Babai d’autre part,
une preuve interactive permet de certifier (rapidement) la réponse à un problème, à condition d’accepter de se soumettre à une série de questions choisies aléatoirement par un tiers. L’histoire qui précède est une variante de l’exemple 8.5 de ce livre.

Au passage, une remarque amusante : dans une version provisoire de ce livre qui circule sur le web, on trouve un exemple un peu différent — les auteurs y expliquent comment convaincre un interlocuteur qu’on fait la différence entre deux boissons gazeuses caféinées...

Mon histoire s’arrête là, mais je vous sens impatient d’en savoir plus.
Si c’est le cas, restez au café, et reprenez-en un, car ça va devenir
un peu plus compliqué.

 La théorie de la complexité

La théorie de la complexité se propose d’étudier quels problèmes sont résolubles de façon mécanique, algorithmique, notamment à l’aide d’un ordinateur — techniquement, une machine de Turing.
Elle met surtout l’accent sur les contraintes requises pour la solution à un tel problème : combien de temps prend-elle en fonction des données ? combien d’espace mémoire requiert-elle ? En fonction de la façon d’évaluer cette complexité et des moyens donnés à une machine, les spécialistes ont alors identifié près de 500 classes de problèmes regroupées dans un impresionnant zoo.
Les classes les plus importantes s’appellent P, NP, et PSPACE (ces sigles sont les abréviations de Polynomial time, Non deterministic Polynomial time et Polynomial SPACE) :

  • La première, P, est la classe des problèmes qu’une machine peut résoudre en un temps polynomial en la taille des données qui lui sont soumises ; grosso modo, c’est la classe des problèmes faciles à résoudre.
  • La deuxième, NP, est la classe des problèmes dont une machine peut vérifier une solution en temps polynomial en la taille des données.
  • La troisième, PSPACE, est la classe des problèmes qu’une machine peut résoudre en utilisant un espace mémoire polynomial en la taille des données.

Les spécialistes essaient de comprendre les relations entre ces différentes
classes ; en ce qui concerne ces trois-là, on a des inclusions.

  • Tout d’abord, P est contenu dans NP, autrement dit : si vous savez résoudre un problème, vous savez aussi vérifier une solution.
  • De même, P est contenu
    dans PSPACE : dans le modèle des machines de Turing, comme pour un vrai ordinateur, cela prend un peu de temps d’accéder à une case mémoire. Donc en un temps polynomial en la taille des données, une machine ne peut accéder qu’à un espace mémoire de taille polynomiale.
  • En fait, NP est lui-même contenu dans PSPACE : si on sait qu’un problème dispose d’une preuve vérifiable en temps polynomial, on peut écrire successivement chaque preuve potentielle, regarder si c’en est une et sinon passer à la suivante. Le point est qu’à chaque étape, on peut réutiliser le même espace mémoire pour vérifier si la nouvelle « preuve » en est bien une.

La question cruciale du domaine est de savoir si P est égal à NP : si un problème dispose d’une solution vérifiable rapidement, peut-on deviner rapidement cette solution ? Les spécialistes pensent bien sûr que non, mais personne n’en a la preuve...

 Preuves interactives

Comme je l’ai déjà dit, la théorie de la complexité introduit la
notion de preuves interactives. Elle nomme IP (pour Interactive Polynomial time)
la classe des problèmes qui possèdent une preuve interactive
courte.

Précisément, un problème appartient à IP si l’on peut trouver deux machines, un « prouveur » et un « vérificateur ». Le prouveur donne la réponse au problème ; pour cela, il accepte de se soumettre à une série de questions du vérificateur. Si la solution est correcte, le prouveur doit répondre convenablement avec probabilité 1 ; sinon, il ne peut répondre convenablement qu’avec une probabilité < 1. De plus, si le prouveur peut utiliser une puissance de calcul illimitée, le vérificateur ne dispose que
d’un temps polynomial.

Les problèmes NP appartiennent évidemment à IP : si vous avez une preuve courte, vous pouvez la donner au vérificateur qui la vérifiera en temps polynomial.
Mais sinon, les problèmes typiques qui appartiennent à IP sont de nature négative : démontrer que deux graphes ne sont pas isomorphes,
qu’un entier n’est pas un résidu quadratique,... ou que deux chaussettes sont de couleurs différentes.

Dans l’exemple de ce texte, mes enfants étaient le prouveur et j’étais le vérificateur : si les chaussettes avaient été de même couleur, ils n’avaient qu’une chance sur deux de répondre correctement, mais comme elles étaient bien de couleurs différentes (et qu’ils ne sont pas daltoniens, eux...), ils ont pu répondre correctement à chaque fois.

L’un des résultats spectaculaires concernant les preuves interactives est le théorème d’Adi Shamir (1992) : la classe IP est égale à la classe PSPACE. Autrement dit, si un problème ne requiert qu’un espace mémoire polynomial pour être résolu, il sera possible d’imaginer un protocole qui en certifiera la réponse en temps polynomial.

Post-scriptum :

Je remercie pour leur relecture attentive Serge Cantat, Loren Coquille, Nicok, Subshift, Frédéric Paccaut, Patrick Popescu-Pampu, Nicolas Tholozan.

Article édité par Patrick Popescu-Pampu

Partager cet article

Pour citer cet article :

Antoine Chambert-Loir — «Je suis daltonien, mais je m’en sors...» — Images des Mathématiques, CNRS, 2012

Crédits image :

Image à la une - Goaneo, http://commons.wikimedia.org/wiki/File:Chaussettes-01.png

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM