Où est Charlie ?

eudi 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¹Un 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. , vérifier des démonstrations ²Au 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. , 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 ! ».