Où est Charlie ?

Le 30 octobre 2011  - Ecrit par  Pierre Colmez Voir les commentaires (3)

Jeudi dernier, Avi Wigderson
est venu donner un colloquium dans lequel il nous a parlé
de tas de choses touchant à l’utilisation des probabilités
pour fabriquer des algorithmes efficaces
 [1], vérifier des démonstrations
 [2],
convaincre sans donner d’information.
Au cours du repas qui a suivi, quelqu’un a présenté une
illustration du concept de preuve sans information que je trouve
particulièrement frappante.

Votre petite fille vient vous
voir avec son livre de Charlie et dit « Je suis sûre qu’il n’y a pas de Charlie dans cette image. » Après un examen intensif, vous finissez par
dénicher Charlie et vous lui dites « Si, si il est là », et elle
de répondre « Je ne te crois pas ! ». Comment faire pour la convaincre
sans lui donner aucune indication pour qu’elle ait le plaisir de
le trouver toute seule ? Vous prenez une feuille de papier journal
beaucoup plus grande que le livre et vous découpez un trou
de la forme de Charlie que vous placez sur le Charlie de la page (en vous
cachant pour qu’elle ne puisse pas voir ce que vous faites), et vous
lui annoncez triomphalement « Regarde, le voilà ! ». Mais vous
avez affaire à une petite fille très méfiante qui répond
« Tu essayes de me rouler : tu as pris un Charlie dans une autre page ! ».
Alors vous prenez une seconde feuille de journal et vous lui proposez
de procéder comme suit : "Je vais mettre la feuille trouée sur le
Charlie et je la recouvre avec l’autre comme ça tu ne vois rien.
Tu choisis d’enlever la feuille du dessus ou les deux feuilles à la
fois et on recommence autant de fois que tu veux. Si j’ai trouvé Charlie
et que tu enlèves une feuille tu verras le Charlie sans savoir où il est
sur la page, si tu enlèves les deux d’un coup tu constateras que je
n’essaie pas de tricher en te montrant un Charlie d’une autre page ; par contre, si je n’ai
pas trouvé Charlie et que j’essaie de te rouler, tu m’attraperas une
fois sur deux : si j’ai choisi de te montrer la bonne page, tu constateras
que je ne sais pas où est Charlie chaque fois que tu enlèves
juste la première feuille, si j’ai choisi un Charlie d’une autre page,
tu le verras à chaque fois que tu décides d’enlever les deux feuilles
d’un coup. Au bout de 20 fois, j’espère que tu seras convaincue
que j’ai vraiment trouvé Charlie !".

Notes

[1Un résultat assez incroyable est que si on dispose d’un problème
difficile (i.e. non soluble en temps polynomial), par exemple si colorier
un graphe avec 3 couleurs l’est (ce que tout le monde croit mais....),
alors on peut transformer tout algorithme probabiliste efficace
(i.e. donnant la réponse avec une grande probabilité en temps
polynomial) en un algorithme déterministe un tout petit peu
moins efficace.

[2Au congrès international à Hyderabad, Irit Dinur nous a donné
un joli exposé
sur les démonstrations vérifiables de manière probabiliste. Voir aussi ce billet. L’image qu’elle a utilisée pour illustrer le concept
est la suivante : imaginez que vous ayez une
tranche de pain gigantesque (c’est la démonstration),
un couteau, et que vous voulez savoir si
quelqu’un a mis de la confiture invisible (une erreur) ou pas sur la tranche
de pain en goûtant en le moins d’endroits possible.
La solution est de commencer par passer le couteau sur le pain
de manière à répandre partout la confiture
éventuelle. Une fois ceci fait, il n’y a plus qu’à
tester au hasard pour décider avec une probabilité raisonnable
de l’existence ou de la non existence de confiture ; et on peut
recommencer autant de fois qu’on veut pour diminuer l’incertitude.
Il y a un algorithme théorique correspondant au passage
du couteau sur la tranche de pain ; il permet de transformer
(en théorie...)
toute démonstration mathématique en une démonstration
vérifiable de manière probabiliste.

Partager cet article

Pour citer cet article :

Pierre Colmez — «Où est Charlie ?» — Images des Mathématiques, CNRS, 2011

Commentaire sur l'article

  • Où est Charlie ?

    le 30 octobre 2011 à 08:53, par hgsvrm

    ... en « tant » poynomial... ?

    Répondre à ce message
    • Où est Charlie ?

      le 20 décembre 2011 à 22:23, par Carole Gaboriau

      J’ai changé en « temps ». Merci !

      Carole Gaboriau
      Secrétaire de rédaction

      Répondre à ce message
  • Où est Charlie ?

    le 30 octobre 2011 à 19:39, par Simon Billouet

    Tu as une référence sur ta première note en bas de page ? (les algorithmes probabilistes). Merci !

    Répondre à ce message

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