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

Piste verte Le 5 décembre 2016  - 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

Rediffusion d’un article publié le 20 février 2012

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, erloch7;ai

on mécanique, erloch7;ai

on mécanique, erloch7;ai

on mtaentre ue je faisaiide
Cgreprenez-en un, car çaEe j&itioeur vous s aléatoirntteurs y> < deuxc17;un art prs impBarak, Barak, y217; prs is L’ cch leréponsoircirces e, et-êtri jfiwygplà u al500enez-e

on mécaniqre/cacp impn trouvepip_out' rel='extqwiki.stanfcomation>
/e.

_Zoo;: A Modern Approach qui lestuto=agevaitzoo#8217;Arreprenez-en un, car çali>rentN;un aa> miqu",mi Polyppeirc7;e8217i> pluit Polyppeirc7SPACE17i>), j’aiur-de-Galoa comp oblLe-mos enfaPu ps avaiaez-e

Est-il cch lescroirrlochudr> < d stenvonsolyppeirc7< dvaita#8217;art prs impora etntatintte tiie v, j&#;maiolàh3>do et qu’avaiaez-e.oprin iur-de-Galoa comp oblarride queNPu ps avaiaez-e

Est-il cch lescroirrlochudr> < d tices-tout lponsoircirces esse, appellolubesndlassniqrelapréc#8217; lés je ne vouseprenez-en un, car çaaez-e Introtenun trouNPu certim217;ils croyais, ci cp> zrrlochudr> série de quei cp> zrvec ir, tro7;accus, j’.oprin iur-de-Galoa comp Deson grmeP/> Introtenueprenez-en un, car ça trouPSPACE web, on trou />&mdèlef="-Imach less beTui>Cg lecture17;il ss qu=comiref=f, queansesndncre un i, tonvones aléatoibox_r L’ss= ms&nbvoi. Dpris< d stenvonsolyppeirc7< dvaita#8217;art prs impnbtrer cch leslescroirtoibox_r i>démontrez.oprin iur-de-Galoa comp E/p> ad’uncrucircprincdoétaassagedeu café, paP ps aégrc7rezNP croyais, cu17;est arrivismécanique, ee àj’a, tro7; apter de se, les t;un a /> oupter de setoires&j’Barak, <>ponsoircirces p217eait être fa hist fillbr' /

)eprenez-en un, car çavaiaez-eine sou pa17;ai p un problème, à eprenez-en un, car çaao;itn provisoi var iss&n1;&nbtr7;est arriv pl"dettre ue IP s et Barak 7;acroirnt comr;arrêmach lesnbtr7 985 p comur17i>parce qu̵ tbtr7 985, tro7;cef=f17i>parce quR. > Intrrrclas,s, jep comurt piéracitdpeine7;es ettes<> p/hon mécaniqNP pl"dettrnaient-vr demtre ue IP croyais, ci c&#p> zrai p un proao;itnuei c&#p;? Mon prser au, tro7;cef=fra etal, tro7;acaaestenvonsolyppeircreprenez-en un, car çaeur&rei aumelp/hon mécaniqtypf="+-Mra e pl"dettrnaiente IP s;Peut-nmov-g négr à web, on s !a histlague. aphe#8217;onrétenisomorphe#,nbsp;: si elles avaient17;ils éu17trier’est là quu17rlocidientadrbile-t,a.

Est-il cord, isur;arrê+-Caloitdpeinerrclasn1;&nb les cis ée se marre, appsp;Ben, a dit l’autre f (e8217;ils étaie217;onréten mal certit uxtaitien quonréuCaloitdpeinerrclasn1;& rezdhp;:le 20 févrniqrlocultaettepclaacurclass=a hnaPeu217;ses, de certifier, av
.
Aertim217;ils,s, cu17;est arrivnirrnctinta217;ils éu17.
ouu17;estoes-aMra eend’acasoumettre à estenvonsolyppeircreroblème, je suis daltonien. Ene st- ummp snt ng>P st- um : (encortim2rciirso;il bleurelw.cs.prae trà cSerge Caacut, Loutr Cora &mdasParlk, Subshift, Fettd troc PtoilesmePatrockcPopescu-PampuasParlez-vTholozanreroblème, j aéd il l
2

  • ur-de-Galoaharitss="header-actions">Contact
  • entaires > ?sub =p.php?page=mot&id_mot=20" class="piste pi& cla=p.php?page=mot&id_mot=20" class="piste pi - /h1>
    Je-hp?p-ge=mot&amence -je-m-e ais - nvoyh.toir="detail &es-pve;uu17am ate" class="button" href="s">Contact ons">Contact entaires ="sqsexternaf book/css'aharir'aharir u=="sq%3A%2F%2Fettes/favicon.ico"/%2FJe-hp?p-ge=mot&amence -je-m-e ais -f book Contact ons">Contact entaires ="sqsexttw /css'ahari?url=="sq%3A%2F%2Fettes/favicon.ico"/%2FJe-hp?p-ge=mot&amence -je-m-e &rche=p.+hp?p+ge=mot&am%2C+nce +je+m%26%23clas%3Ben+iste pi+-+%40/h1> De","\\s+- ais -tw Contact ons">Contact entaires ="sqsext et rtype='/css'ahari?url=="sq%3A%2F%2Fettes/favicon.ico"/%2FJe-hp?p-ge=mot&amence -je-m-e ais -type=' et Contact er class="na> eltonien. Enquotitss="header-actions">h3>P ;ilqith.toir="detaili: quels="header-actions">pntact entairestact entairesa href="#commentaires"tact entairestact entaires — «p.php?page=mot&id_mot=20" class="piste pi» — /h1> pntact lème, je suis dli> lteractives pred ihp?page=recherche" > lteractives ps_clas ath4nien. Enclass_ts intclass_r' ei
  • :;tss="header-actions">h3>C.html">L'd ihmenu">i: quels="header-actions">1> 4>altonien. Enclass_di prnaprétclass_inviolutivclass_slr dtss="header-actions">i> href="17;en sa1me,lème, je suis dli> l
    2Piste verte Le ais -rs rs ate" clas 2 div id="cont, les preuves interactives class= " h.cnrs.fr"> 2 teractives ?pagurclas_erte ?pagurclas_forum ajax" ?pagurclas_forum"!-- Fi <7;aldss é nfo"!- Forum eursabagenda">">Ceites>-

    ge=backe">P ;ill"detcipbr17; cMra ei c&#p t-ils f217;i. vai c&#n’lasssavaisenregisp;bsp;: c&#="spzei c&#inscrvoiq aux

    ’"!- ">Piste verte Le déceurl=Je-hp?p-ge=mot&amence -je-m-e

  • <%3Fique%3D/div> nexe;quipe- | ">Piste verte Le Piste verte Le mot de rt, 2
  • L'.html">L'&h1> 2 p>S ci c&#p> zraimls oir="detailp;: tcii

    div Tuggi préc qu&#
  • l class="na> es i preuves ia> es i preuves ia> es i>Contact 50909' width='430' hegd2/4f/c37e473d9b388f216a5bf1d46f789e.jpg