Étiquette : maths

En vrac

Publié le par BaliseLaisser un commentaire

640px-Vis_en_vracHop, c’est dimanche, c’est vrac. Juste pour information, le premier et le dernier lien de la liste sont des articles assez longs.

  • Eugenics, Ready or Not, un article extrêmement dérangeant mais très intéressant qui explore les conséquences d’un eugénisme plus ou moins développé sur la société humaine, et sur ce qu’il se passe déjà dans le domaine. Ya de la matière à SF dystopique, mais on en est pas forcément si loin que ça… (en anglais)
  • Will Computers Redefine the Roots of Math? – le titre est assez nul, l’ancien titre qui semble toujours être sur la page, Univalent Foundation Redefines Mathematics est certes moins accrocheur, mais a vachement plus à voir avec le contenu de l’article 🙂 Ça cause d’axiomes de base des maths, de topologie, j’ai pas tout compris sur la fin, mais la vue d’ensemble était intéressante (en anglais)
  • NSA in P/poly: The Power of Precomputation – un billet agréable à lire sur les derniers événements autour du fait que Diffie-Hellman est en pratique moins sûr que ce qu’il pourrait/devrait être en théorie, avec quelques calculs divers sur le concept « et donc, si la NSA-ou-autre-agence-gouvernementale voulait faire ça, ça leur prendrait combien de moyens/temps/etc ? » (en anglais)
  • Beach reading (and More) – quand Bill Gates part à la plage, il emmène pas de la littérature-à-vampires, mais tout un tas de trucs que je lirais bien aussi. (en anglais)
  • Dossier Pour la Science n°82 (janvier 2014) : L’évolution des langues – moi, j’aime bien quand Christophe il résume les Pour La Science, parce que je vois vaguement passer des trucs que je verrais pas passer du tout autrement. On me dira que j’ai qu’à m’abonner à PLS, ce à quoi je répondrai « certes. » (en français)
  • http://emot.es/ – un site web débile qui recense tous les smileys débiles à base de caractères étranges qui fleurissent ici et là. Une bonne source de copier-coller 😛 (en emotes)
  • Using millions of online photos cobbled together, we can now watch history unfold – toi aussi, récupère moult images prises à peu près du même endroit sur Flickr et Picasa et assemble-les pour faire des vidéos qui montrent le passage du temps. Rigolo. (en anglais, mais les vidéos sont très visuelles)
  • De l’impression par film hydrographique assistée par ordinateur – c’est SIGGRAPH dans quelques mois, du coup on commence à voir fleurir tout un tas de vidéos de présentations de papier ouachement cools, et celle-ci en fait partie (en français, mais la vidéo est en partie en anglais)
  • Apollo 13, we have a solution – un chouette article publié pour les 35 ans de la mission Apollo 13 (et donc il y a dix ans) – qui parle du sauvetage de la mission. Relativement long (l’adresse que je donne ici n’est que la partie 1/3, les deux autres sont liées à la fin), mais ça vaut le coup (en anglais).

TPA : Théorème de Ramsey

Publié le par Balise2 commentaires

Je viens de me rendre compte que j’avais pas encore parlé de théorie de Ramsey dans ce blog, ce qui est profondément scandaleux, parce que c’est un sujet très rigolo. Donc, commençons – aujourd’hui, c’est TPA.

Supposons que nous ayons un graphe dit « complet », c’est-à-dire qu’on se donne un ensemble de sommets, et qu’on trace tous les arcs possibles entre tous les sommets. On dénote par K_n le graphe complet sur n sommets - par exemple, je vous présente K_5 :

 

k5-mono

Maintenant, on va colorier les arcs du graphe en rouge et en bleu, de façon arbitraire. On peut par exemple colorier tous les arcs en bleus, tous les arcs en rouge, ou choisir d’autres coloriages :

Et avec ce coloriage, on se pose une première question : est-ce qu’il est possible d’avoir un coloriage tel qu’on ne puisse pas trouver dans la figure un triangle bleu ou un triangle rouge, c’est-à-dire trois sommets reliés uniquement par des arcs bleus ou rouges ? Les deux du haut ne fonctionnent clairement pas (puisque tous les sommets sont reliés par des arcs bleus et rouges respectivement). Le coloriage en bas à gauche ne fonctionne pas non plus : il a un triangle bleu et un triangle rouge (vous les voyez ?). Le coloriage en bas à droite n’a pas de triangle rouge, mais il a un triangle bleu.

Pour 5 points, ce n’est pas très difficile de finir par trouver un coloriage qui ne contient ni triangle bleu ni triangle rouge, et c’est celui-ci :

k5-notriangle

L’étape suivante est de se poser la même question non pas avec un graphe complet sur 5 sommets (K_5) mais avec un graphe complet sur 6 sommets (K_6), comme celui-ci :

k6

Et la réponse est non, ce n’est pas possible : on ne peut pas colorier une K_6 avec deux couleurs en évitant d’avoir un triangle monochromatique (tout bleu ou tout rouge, donc). La première remarque qu’on peut faire, c’est que pour vérifier par force brute que c’est effectivement le cas, ça va prendre un petit peu de temps. Le graphe ci-dessus a 15 arcs, ce qui correspond à 2^{15} coloriages différents. Pour voir ça, on peut choisir un ordre pour les arcs (n’importe quel ordre) et commencer à colorier. Pour le premier arc, on peut choisir rouge ou bleu, ça fait deux choix. Pour le deuxième arc, idem – et on a déjà quatre choix avec deux arcs, puisqu’ils peuvent être tous les deux rouges, tous les deux bleus, rouge-bleu ou bleu-rouge. Le troisième choix multiplie encore ces choix par deux (puisque chaque choix peut correspondre à un troisième arc rouge ou bleu), et ainsi de suite pour les 15 arcs, soit 2×2×2×…×2 = 2^{15}. 2^{15}, ça fait 32768. À la main, ça va faire beaucoup de coloriages à vérifier, mais sur un ordinateur, ça reste encore nettement dans le domaine du faisable.

Avant de programmer le coloriage et de vérifier, on peut se demander s’il y aurait moyen de prouver qu’il y a toujours un triangle monochromatique dans une K_6 coloriée avec 2 couleurs. Donc, on prend un coloriage, n’importe lequel. On prend un sommet, n’importe lequel aussi. Ce sommet, il a 5 arcs qui y sont connectés, et parmi ces cinq arcs, il y en a au moins trois qui sont de la même couleur (parce que si j’ai au plus deux arcs bleus ET au plus deux arcs rouges, ben j’ai au plus 4 arcs). Pour faire simple, je vais supposer que les trois arcs qui sont de la même couleur sont bleus (je peux toujours faire ça, si ce n’est pas le cas il suffit de remplacer rouge par bleu et bleu par rouge dans ce qui suit). Maintenant on fait une petite figure avec des notations.

k6-firstcolors

J’ai au moins trois arcs bleus qui partent de mon sommet initial, j’en choisis exactement trois (les deux autres peuvent être rouges ou bleus). Ces arcs définissent trois points sur le graphe, qui sont les autres extrémités des trois arcs ; je nomme ces points u, v et w. Et là, il peut se passer plusieurs choses. Si l’arc entre u et v est bleu, alors j’ai un triangle bleu. Si l’arc entre v et w est bleu, alors j’ai un triangle bleu. Si l’arc entre u et w est bleu, alors j’ai un triangle bleu. Et si rien de tout ça ne se passe…

k6-plusred

ben l’arc entre u et v est rouge, l’arc entre v et w est rouge, et l’arc entre w et u est rouge aussi, donc le triangle défini par u, v, w est tout rouge. Tout ce que j’ai raconté là s’applique à n’importe quel coloriage (même s’il faut éventuellement changer rouge en bleu et bleu en rouge), et donc on ne peut pas trouver de coloriage qui n’ait ni triangle bleu, ni triangle rouge.

La remarque suivante, c’est que n’importe quelle K_n (c’est-à-dire un graphe complet sur n sommets), pour n \geq 6, contient une K_6. Donc si on ne peut pas colorier une K_6 sans avoir de triangle monochromatique, on ne peut pas non plus colorier une K_n, n\geq 6 sans triangle monochromatique.

Donc, pour les triangles, on sait ce qu’il se passe : pour n\leq 5, on peut trouver un coloriage tel qu’on ne trouve pas de triangle monochromatique, et pour n \geq 6, on a prouvé qu’il n’existait pas.

La question suivante est : maintenant qu’on a des choses pour les triangles, est-ce qu’on peut avoir le même genre de résultat pour plus de points ? Plus spécifiquement, si je considère une K_n, est-ce que je peux la colorier avec deux couleurs de manière à éviter d’y trouver une K_4, K_5, K_6, K_{42} de la même couleur (remarquons qu’un triangle est une K_3 😉 )? Et ben, c’est une question compliquée. Pour être sûr de trouver une K_4, il a été prouvé qu’on a besoin de 18 points. Ce qui veut dire qu’on peut colorier ce bidule-là avec 2 couleurs et ne pas y trouver de K_4 monochromatique:

K17

Si on rajoute un sommet et qu’on le connecte à tous les autres, par contre, on est sûr de trouver une K_4 monochromatique si on colorie avec deux couleurs. Là, pour le coup, si on veut réellement vérifier tous les coloriages possibles, il va vraiment falloir faire des progrès sur la puissance informatique. Une K_{18} (un graphe complet sur 18 sommets, donc) a 153 arcs, donc si on se mettait en tête de vérifier tous les coloriages, il faudrait en vérifier 2^{153}. Si on est capable de vérifier un coloriage par nanoseconde (ce qui n’est pas franchement réaliste), il faudrait plus de 3 000 000 000 000 000 000 000 000 000 (3 suivi de 27 zéros) SIÈCLES pour tout vérifier… on est pas rendu 🙂

Là où ça devient VRAIMENT amusant, c’est quand on se pose la question de trouver des K_5 et supérieur (qui soient monochromatiques, donc). Pour la K_5, on sait que pour plus de 49 sommets, on la trouvera nécessairement. On sait aussi qu’on peut construire un coloriage sur 42 sommets sans K_5 monochromatique. Le lecteur attentif aura remarqué qu’on ne sait pas ce qu’il se passe entre 43 et 49 sommets… La situation est de moins en moins claire au fur et à mesure : pour la K_{10} monochromatique, on sait que le seuil se situe quelque part entre 798 (pour 797 sommets on sait qu’on peut colorier sans avoir de K_{10} monochromatique) et… 23556 (pour un graphe complet sur 23556 sommets colorié avec deux couleurs, on sait qu’on aura toujours une K_{10} monochromatique).

Le théorème de Ramsey qui donne son nom à ce billet de blog dit que quelque soit r, on peut trouver un n tel que tout coloriage avec deux couleurs d’une K_n contienne nécessairement une K_r monochromatique. Ledit théorème est plus général que ça : il dit que pour tout r_1, r_2, r_3... r_\ell on peut trouver un n tel que tout coloriage de K_n avec \ell couleurs c_1, c_2,..., c_\ell contient ou bien une K_{r_1} de couleur c_1, ou bien une K_{r_2} de couleur c_2, …, ou bien une K_{r_\ell} de couleur c_\ell. Et on dénote n par R(r_1, r_2,..., r_\ell). (Pour rattacher aux trucs précédents, j’ai démontré que R(3,3) = 6, et j’ai indiqué que R(4,4) = 18, 43 \leq R(5,5) \leq 49 et que 798 \leq R(10,10) \leq 23556.

On peut exprimer ça de façon plus « philosophique » en disant qu’une structure suffisamment grande aura toujours un peu d’ordre local quelque part. Ce que je trouve personnellement assez fascinant.

Le mot de la fin revient à Joel Spencer: « Erdős nous a demandé d’imaginer une force d’extraterrestres, beaucoup plus puissante que nous, qui atterrit sur Terre et nous demande la valeur de R(5,5), ou bien ils détruisent la planète. Dans ce cas, dit-il, nous devrions combiner la puissance de tous nos ordinateurs et de tous nos mathématiciens pour tenter de trouver la valeur. Mais supposons qu’ils demandent R(6,6). Dans ce cas, il pense qu’il faudrait détruire les extraterrestres. » (traduction personnelle).

Algorithmes aléatoires et conflits sur l’échiquier

Publié le par Balise1 commentaire

J’avais dit que je ferais un billet sur les algorithmes aléatoires, et je ne l’ai toujours pas fait. Une petite part de flemme, et une grosse part d’infusion – mais je viens enfin de trouver l’exemple raisonnablement rigolo et abordable que je cherchais depuis longtemps…

Le principe de l’algorithme aléatoire, c’est essentiellement « boah, on va faire n’importe quoi, et puis si on fait n’importe quoi suffisamment de fois, on finira bien par tomber sur une solution qui marche ». Le « n’importe quoi » consiste à faire un choix au hasard quand on ne sait pas quoi faire, et le « suffisamment de fois » dépend du « n’importe quoi ». L’idée, c’est que quand on fait les choses au hasard, on a normalement au moins une chance, même infime, de tomber sur une solution. Mais si j’ai, par exemple, une chance sur 1000 de tomber sur la solution à mon problème, si j’exécute la même procédure aléatoire indépendamment 1000 fois, j’ai de bonnes chance de tomber sur ce que je veux. Je ne peux pas garantir à 100% que je vais trouver la solution, mais… Tiens, d’ailleurs, quelle est la probabilité que ça marche en faisant 1000 essais ? C’est un petit exercice assez facile, peut-être qu’un petit rappel de probabilités peut être utile (voir la partie 1 et la partie 2)… Je vais tout de même donner la solution. La probabilité que l’algorithme retourne le bon résultat est 0.001. La probabilité qu’après 1000 fois ça ait réussi au moins une fois, c’est 1 – la probabilité que ça ait échoué toutes les fois. La probabilité que ça échoue, c’est 0.999. Comme mes exécutions sont indépendantes, je peux multiplier les probabilités de tous ces essais entre elles : ça fait 0.999^1000, c’est à dire environ 0.368. Donc, la probabilité que ça ait réussi après 1000 essais est de 0.623. Ce qui peut paraître assez faible, ça fait moins de trois chances sur quatre. Mais si je répète, non pas 1000 fois, mais 3000 fois, j’obtiens une probabilité de succès de 1 – 0.999^3000, soit environ 0.95… Et on peut continuer à répéter pour avoir la probabilité de succès que l’on souhaite obtenir, même avec des probabilités de succès initiales très faibles. Si l’algorithme lui-même n’est pas trop violent en terme de calculs, n’importe quel ordinateur est tout à fait capable d’exécuter ça en un temps correct. Et les algorithmes aléatoires peuvent souvent se permettre d’être très simples – plutôt que de calculer un machin compliqué à calculer, pouf, on met une valeur au hasard et on espère que ça marche.

Ça peut paraître un peu fou comme approche, mais comme j’ai essayé de l’expliquer dans le paragraphe qui précède, on peut en fait faire des choses tout à fait rigoureuses dans le domaine. On prend un algorithme, on calcule la probabilité qu’il renvoie une réponse correcte, de là on déduit combien de fois il faudra le répéter pour avoir une probabilité de succès qui convient, et on est content. Et de là, il y a deux grosses difficultés. La première, c’est d’arriver à un algorithme qui ne soit pas complètement débile. Si l’espace de solutions est immense et qu’on se contente de prendre un élément de l’espace de solutions au pif, ça va rarement donner des choses intéressantes. Par contre, si on arrive à avoir une approche semi-intelligente, ça permet souvent d’avoir des algorithmes qui ont une espérance de temps d’exécution meilleure que les algorithmes déterministes pour un problème donné. La deuxième grosse difficulté, c’est parfois de calculer/prouver la probabilité de succès d’un algorithme (ce qui permet d’avoir une idée du nombre de répétitions à prévoir et donc du temps d’exécution). Il y a une troisième difficulté, qui n’est pas vraiment liée directement à l’algorithme aléatoire lui-même. On ne sait pas, à l’heure qu’il est, si l’ajout d’une composante aléatoire permet toujours d’avoir des algorithmes plus performants. Il existe des gens (j’en fais partie en ce moment) qui s’intéressent à la question de savoir si un algorithme aléatoire donné peut être transformé de façon magique en un algorithme déterministe (sans hasard, donc) en gardant des performances équivalentes. Il y a aussi des gens qui s’intéressent à la question générale de savoir si l’aléatoire peut apporter quelque chose, ou si la classe des problèmes qui se résolvent « facilement » avec des éléments aléatoires est la même que celle des problèmes qui se résolvent « facilement » de façon déterministe – pour une certaine définition de facilement. (Notons d’ailleurs que les deux questions n’ont pas le même sens, en dehors de la distinction « un algorithme donné / une classe de problèmes » – dans le premier cas on cherche à avoir les mêmes performances, dans le second cas, on est plus souples et on pourrait par exemple se contenter d’un « si je peux résoudre un problème en temps t avec de l’aléatoire, je peux le résoudre en temps t³ sans aléatoire »).

Après ces longs paragraphes introductifs et vaguement philosophiques, je vais donner un exemple à partir d’un problème connu, celui des 8 reines. Ça rappellera sans doute des choses à ceux qui ont joué à The 7th Guest il y a 20 ans. On suppose qu’on dispose d’un échiquier – donc une grille 8×8 – et de 8 pions qui peuvent se déplacer comme une reine aux échecs, c’est-à-dire en ligne horizontale ou verticale, et en diagonale, d’un nombre arbitraire de cases. On dit que deux reines sont en conflit lorsqu’elles peuvent s’attaquer - c’est-à-dire qu’elles sont sur la même ligne horizontale, verticale ou diagonale. On veut placer huit reines sur l’échiquier de façon à ce qu’aucune d’elles ne soit en conflit avec aucune autre. C’est pas complètement trivial comme problème, comme on peut s’en rendre compte en essayant de le résoudre à la main (ça se fait, mais c’est pas immédiat). Là, le problème reste relativement simple, au sens où la grille reste assez petite. Faire le même genre de choses avec 50 reines sur un échiquier 50×50, il y a de bonnes chances de ne pas s’en sortir à la main. Et puis construire un algorithme déterministe pour ce machin, c’est pénible, ça backtracke dans tous les sens, et moi le backtracking ça me fout mal au crâne (c’est pas complètement vrai, il y a un algorithme récursif qui existe aussi, mais bon). Donc, voyons ce qu’on peut faire de manière aléatoire. Je vais me limiter dans certains cas aux 8 reines, parce que ça fait des nombres « gérables ». Et je vais tricher un peu, je vais dégainer la Wikipedia sur le sujet Problème des huit dames, et je vais affirmer qu’il existe 92 solutions au problème – ça me sera utile pour donner certains nombres.

On peut prendre une approche vraiment bourrine – on numérote les cases de l’échiquier de 1 à 64, on tire huit numéros de 1 à 64, et on place une reine sur chaque case. Si ça marche, ben on a fini ; si ça marche pas, on reprend les reines de l’échiquier et on recommence. La probabilité de succès de cet algorithme, elle est pas bien élevée – il y a 4 426 165 368 manières de choisir 8 chiffres parmi 64, ce qui nous donne une probabilité de succès d’environ 2.07 × 10^-8. C’est peu.

Donc, on regarde d’un peu plus près le problème, et on fait une observation facile : si je veux avoir la moindre chance qu’une solution marche, une chose est sûre, c’est que je n’aurai qu’une seule reine par colonne de mon échiquier. Donc, plutôt que de prendre huit numéros de 1 à 64, je prends, pour chaque reine, un nombre au hasard de 1 à 8, et je place la reine numéro k sur la colonne k et sur la ligne correspondant au nombre qu’on a pris au hasard. C’est sensiblement meilleur – ça correspond à 8^8 = 16 777 216 possibilités, soit une probabilité de succès qui tourne autour de 5.48 × 10^-6. C’est mieux, mais c’est toujours pas top.

On fait alors l’observation facile suivante : je n’aurai aussi qu’une seule reine par ligne de mon échiquier. Bon, d’accord, j’aurais probablement pu faire l’observation en même temps que la précédente, mais faut pas me brusquer, on est dimanche matin et j’ai mangé de la raclette hier soir. Donc, plutôt que de prendre un nombre au hasard de 1 à 8 pour chaque reine, je prends une permutation au hasard (c’est à dire que je prends un nombre de huit chiffres dans lequel tous les chiffres de 1 à 8 apparaissent), et je pose mes reines en fonction de cette permutation (la première reine sur la ligne du premier chiffre, la deuxième sur la ligne du deuxième, et ainsi de suite). Ça améliore encore un peu les choses – il y a 8! = 40 320 permutations possibles, soit une probabilité de succès de 2.28×10^-3, soit 0.02%. Ça commence à rentrer dans la catégorie des machins « faisables »… mais uniquement pour des petites valeurs de la taille de l’échiquier. Si on monte, mettons, ne serait-ce qu’à 16 reines sur un échiquier de 16×16 cases, la séquence OEIS kivabien nous permet d’évaluer la probabilité de succès à 14 772 512/16!, soit environ 7.06×10^-7. Le problème, c’est que la factorielle, là, ben elle est quand même encore très moche.

On peut encore améliorer les choses. Il y a trois sources de conflits pour les reines sur l’échiquier : les lignes horizontales, les lignes verticales, et les diagonales. L’approche par permutations permet de gérer les deux premières, mais y ajouter la gestion des diagonales commence à filer VRAIMENT mal au crâne (on se retrouve à faire des machins du genre « si j’ai deux chiffres qui sont dans des positions qui diffèrent de k, ils ne peuvent pas différer eux-mêmes de k », et c’est imbitable). Par contre, ce qu’on peut faire assez facilement, c’est générer la permutation petit à petit. L’idée, c’est qu’on place les reines une par une au hasard dans une colonne, en supprimant toutes les lignes qui sont en conflit avec une reine placée précédemment.  Donc, on place la première reine au hasard sur la première colonne, la deuxième reine au hasard, mais de façon à ce qu’elle ne soit pas sur la ligne de la première ni sur ses diagonales, et ainsi de suite. Et si on ne peut pas trouver une position sans conflit dans la colonne, c’est que la solution courante ne marche pas – on vire tout et on recommence du début. Je n’ai pas trouvé d’analyse rigoureuse de ce machin, et j’ai la flemme de la tenter moi-même (je soupçonne accessoirement ne pas être capable de m’en sortir, du moins pas dans un temps qui me permette de publier ce billet rapidement), mais il y a au moins une implémentation qui a été testée sur 1000 reines avec des temps d’exécution raisonnables (variant apparemment de 39 secondes à 25 minutes). L’idée, cela dit, c’est qu’on élimine beaucoup de permutations de l’espace de recherche : par exemple, on supprime toutes celles qui commencent par « 12 » – ce qui correspond, pour un problème de 8 reines, à 720 permutations, ce qui n’est pas énorme, mais si on multiplie ça par 14 (parce qu’on supprime aussi celles qui commencent par « 23 », « 34 »,…, « 78 », « 21 », « 32 »,…,« 87 »), à 10 080 permutations, soit déjà un quart de l’espace de recherche ! Plus l’échiquier est grand, moins ces deux premières étapes seront significatives (et plus le « un quart » va tendre vers 0, si vous me passez l’expression), mais l’idée reste la même : on réduit l’espace de recherche, et la probabilité de succès augmente.

Toutes ces approches ont la même base : on recherche une combinaison qui fonctionne dans tout l’ensemble des combinaisons, en essayant de supprimer les combinaisons qui ne marchent pas le plus tôt possible. Il existe un autre type d’approche, qui est celle de la « réparation ». L’idée, c’est que pour une permutation donnée, on n’est peut-être pas loin d’une solution qui marche. Donc, plutôt que d’explorer l’espace de combinaisons entier, on peut peut-être explorer autour d’une permutation en essayant de se rapprocher d’une solution. Une solution, par définition, c’est une combinaison qui a zéro conflit. Donc, on peut supposer qu’on se « rapproche » d’une solution quand on diminue le nombre de conflits. C’est l’idée du dernier algorithme que je vais présenter dans ce billet. On commence par prendre une permutation aléatoire qui « a une bonne tête » en utilisant l’algorithme précédent et, au lieu de s’arrêter lorsqu’on rencontre un conflit, en plaçant une reine au hasard sur l’une des cases présentant le nombre minimum de conflits de la colonne. Si elle marche, tant mieux, on a fini. Sinon, on choisit une colonne au hasard, et on compte, pour chaque case, le nombre de conflits auquel elle correspond, en ne comptant qu’un seul conflit si plusieurs reines génèrent ce conflit (parce de toute façon elles sont alors en conflit entre elles, et il faudra gérer ça). S’il existe une case pour laquelle la reine de la colonne courante aurait moins de conflits, on la déplace (en choisissant au hasard la case si plusieurs d’entre elles ont le même nombre de conflits). Et on recommence. Il n’y a en revanche pas de garantie que cet algorithme va toujours renvoyer une solution : si on n’a pas de chance, on peut se retrouver dans un minimum local, ne pouvoir améliorer le nombre de conflits sur aucune colonne, et boucler infiniment. Il faut prendre ce genre de cas en compte, et arrêter/recommencer l’algorithme si le nombre d’étapes commence à exploser vraiment trop violemment. Là, vraiment, je sais que l’analyse de cet algorithme va au-delà de ce que je veux présenter sur ce blog (j’avoue ne pas l’avoir lue, surtout qu’il manque des figures sur le papier). Le papier qui présente la méthode indique que le nombre de conflit réparés reste à peu près constant quel que soit la taille de la grille, et qu’ils arrivent à résoudre le problème sur un échiquier d’un million de cases de côté en 4 minutes. Sur une SPARCstation 1, en 1991.

Bref, les algorithmes aléatoires, c’est rigolo et utile. Je pense qu’un prochain billet discutera des algorithmes aléatoires pour SAT, parce que c’est quand même ce sur quoi je passe beaucoup de temps en ce moment. J’ai quand même passé un truc assez fondamental sous le tapis, c’est que générer des nombres aléatoires, c’est hautement non-trivial. En pratique, ce que j’ai présenté ici fonctionne aussi avec des nombres « à peu près aléatoires » tels qu’un ordinateur est capable de les générer. Mais ceci est une autre histoire, que nous vous raconterons une prochaine fois… ou pas, parce que là, j’ai pas le niveau 😛

Raisonnement par récurrence et raisonnement par l’absurde

Publié le par Balise5 commentaires

Pouf pouf, un petit billet vite fait pour pouvoir y faire référence plus tard – je suis en train de faire un autre monstro-billet, et je me suis rendue compte que j’avais besoin des éléments suivants pour faire un truc qui tienne à peu près debout, donc hop, un deuxième billet ! Je vais causer ici de deux outils fondamentaux dans la « boîte à outils » nécessaire pour prouver des trucs : le raisonnement par récurrence et le raisonnement par l’absurde. Ce sont des outils qui sont présentés et utilisés au moins au lycée (du moins de mon temps 😉 ), et qu’on retrouve à longueur de temps, partout, donc autant expliquer comment ça marche.

Le raisonnement par récurrence

Le principe du raisonnement par récurrence, c’est les dominos. Pas ceux avec des points, ceux qu’on fait tomber. On sait que si on fait tomber un domino, le suivant tombe aussi. Et on fait tomber le premier domino. Du coup, tous les dominos tombent.

Pour le raisonnement par récurrence, c’est pareil. On a une propriété qui dépend d’un entier, et on veut prouver qu’elle est vraie pour n’importe quel entier. Donc ce qu’on fait, c’est qu’on commence par montrer qu’elle est vraie pour un petit entier, genre 0, 1, 2 (parfois les cas pour 0 ou 1 n’ont pas beaucoup de sens). Et on montre que si elle est vraie pour un entier k, alors elle est vraie aussi pour un entier k+1. Du coup, on a le « départ » des dominos (« c’est vrai pour 0 ») et le « chaînage » des dominos (« si c’est vrai pour n, c’est vrai pour n+1 ») ; et si ces deux conditions là sont vraies, alors tous les dominos se cassent la gueule (« la propriété est vraie pour tous les entiers à partir de celui qu’on utilise comme cas de base »).

Là, je suis un peu embêtée, parce que j’ai un exemple qui marche, mais la preuve est assez nulle par rapport à une autre, qui est plus jolie. Donc je vais montrer les deux 🙂 Je veux démontrer que la somme des entiers de 1 à n est égale à n(n+1)/2, pour n’importe quel n. Je commence par n = 1 : j’ai bien 1(1+1)/2 = 2/2 = 1, donc l’hypothèse de base est vraie.

Ensuite, je suppose que c’est vrai pour un entier k, c’est à dire que la somme des entiers de 1 à k est égale à k(k+1)/2. Maintenant, je calcule la somme des entiers de 1 à k+1 : 1 + 2 + 3 + … + (k-1) + k + (k+1), c’est égal à la somme des entiers de 1 à k, plus (k+1). Par hypothèse de récurrence, c’est égal à k(k+1)/2 + k+1 = (k² + k + 2k + 2)/2 = (k² + 3k + 2)/2. Pour que ma preuve fonctionne, je veux que la somme des entiers de 1 à k+1 soit égale à (k+1)(k+2)/2. Et il se trouve que (k+1)(k+2), ça fait précisément k² + 3k + 2.

J’ai donc mon hypothèse de base, mon étape de récurrence, et j’ai prouvé ce que je voulais prouver.

Pour le fun, la preuve que je préfère sur cette égalité, c’est celle-ci : on considère un tableau à deux lignes et n colonnes :

1  2   3   4 ... n-2 n-1 n
n n-1 n-2 n-3     3   2  1

et on additionne les deux lignes. Chaque colonne vaut n+1 : c’est le cas pour la première colonne, et à chaque étape, on ajoute 1 à la première ligne et on enlève 1 à la deuxième ligne, donc la somme reste identique. (Quelque part, ici, je fais du raisonnement par récurrence sans vraiment le dire !). J’ai n colonnes, donc si j’additionne tous ces résultats, ça fait n(n+1). Et si je fais la somme dans l’autre sens, la première ligne est égale à la somme des entiers de 1 à n, la deuxième ligne aussi… donc mon n(n+1), c’est aussi deux fois la somme des entiers de 1 à n.

Le raisonnement par l’absurde

Le raisonnement par l’absurde est parfois un peu dangereux/délicat, parce qu’il est parfois utilisé à tort et à travers. Admettons que je veuille prouver qu’une phrase A est vraie. L’idée du raisonnement par l’absurde, c’est de partir du principe que A est faux, de dérouler une suite d’arguments impliqués par le fait que A est faux, et d’arriver à quelque chose qu’on sait être impossible. Si le fait que A est faux implique que quelque chose d’impossible arrive, c’est que A est vrai, sinon l’univers se casse la gueule et ça fait désordre.

Mon exemple préféré, c’est de démontrer que \sqrt 2 est irrationnel, c’est à dire qu’on ne peut pas l’écrire sous la forme \frac p q avec p et q des nombres entiers.

J’ai besoin d’une toute petite preuve au passage : j’affirme que si un entier n est pair, alors son carré n² est pair, et que si n² est pair, alors n est pair. Si n est pair, je peux l’écrire comme n = 2k, et donc n² = 4k² = 2 × 2k², donc n² est pair. Si n est impair, je peux l’écrire comme n = 2k+1, donc n² = 4k² + 2k + 1 = 2(2k² + k) + 1, donc n² est impair. Donc si n² est pair, il ne peut pas arriver que n soit impair (parce que sinon n² serait impair aussi), donc n est pair.

Donc, supposons qu’on puisse écrire \sqrt 2 = \frac p q. On peut aussi supposer que la fraction est irréductible, parce que si elle ne l’est pas, on peut la réduire pour qu’elle le soit (rappel : une fraction \frac p q est irréductible s’il n’existe pas d’entier k tel que p et q soient tous les deux divisibles par k. Si k existe, on divise p et q par k, et on considère la fraction \frac{p/k}{q/k}). Donc, je peux écrire que \sqrt 2 \times q = p. Je mets tout au carré, et j’obtiens que 2q² = p². Comme q est entier, q² est entier aussi, et donc p² est pair (puisque c’est deux fois un nombre entier). Mais si p² est pair, alors p est pair aussi, d’après ma preuve auxiliaire. Donc je peux écrire p = 2k, et donc p² = 4k². Mais du coup, comme 2q² = p² = 4k², je peux écrire que q² = 2k², et donc q² est pair, et q est pair. Mais ça, c’est pas possible : la fraction \frac p q est irréductible, donc p et q ne peuvent pas être pairs en même temps ! Donc, j’ai un truc qui ne va pas dans mon raisonnement, et ce truc, c’est mon hypothèse initiale, c’est-à-dire que \sqrt 2 est rationnel. Donc, \sqrt 2 est irrationnel. Joli, non ?

TPA – Planarité, mineurs et donuts

Publié le par Balise3 commentaires

Pour le premier Théorème à Périodicité Aléatoire, on va parler de graphes, et on va faire des petits dessins. Un graphe est un ensemble de sommets reliés entre eux par des arcs. Pour décrire un graphe, je peux par exemple dire « il a les sommets 1, 2, 3, 4 et 5, et des arcs entre les sommets 1 et 2, 2 et 3, 3 et 4, 4 et 1, 1 et 3, 2 et 4, 1 et 5, et 4 et 5 ». Je peux aussi décider de le dessiner sur une feuille de papier, et je peux dessiner ça de plusieurs manières : tous les dessins, là, sont une représentation de ce graphe.

wagner1

Dans ces trois représentations, deux sont dites planes : le graphe est dessiné de façon à ce que les arcs du graphe ne se croisent pas. La première représentation n’est pas plane : les arcs 1-3 et 2-4 se croisent. Un graphe qui peut être dessiné dans le plan (c’est-à-dire sur une feuille de papier plate) sans que deux arcs se croisent est un graphe planaire. Le fait qu’on ait un adjectif pour ça devrait vous faire dire qu’il existe des graphes non planaires, c’est-à-dire qu’on ne peut pas dessiner dans le plan sans croiser deux arcs. Deux exemples classiques (et utiles pour la suite) de ce type de graphes sont le graphe complet sur 5 sommets (je prends 5 sommets et j’ajoute tous les arcs possibles), qu’on appelle en abrégé K_5, et le graphe bipartite complet sur 3×2 sommets (je prends deux groupes A et B de trois sommets et j’ajoute tous les arcs possibles entre les sommets du groupe A et les sommets du groupe B), qu’on appelle en abrégé K_{3,3}. En voici des représentations dans le plan ; comme on l’a vu, ces représentations ne sont pas uniques, mais vous pouvez chercher longtemps avant de trouver une représentation où deux arcs ne se croisent pas.

k5k33

Et le théorème suivant, dû à Wagner en 1937, dit que si un graphe n’est pas planaire, c’est parce que, quelque part dans sa structure, on trouve un truc qui ressemble à K_5 ou à K_{3,3}. Plus précisément :

Un graphe est planaire si et seulement s’il ne contient le mineur K_5 ni le mineur K_{3,3}.

Je triche un peu, parce que je n’ai pas encore défini la notion de mineur. Donc, définissons :

Un mineur d’un graphe G est un graphe obtenu à partir de G en effectuant zéro ou plusieurs suppression d’arc, suppression de sommet ou contraction d’arc.

Supprimer un arc, c’est facile : si deux points sont reliés par un arc, on peut décider qu’en fait non, et supprimer l’arc. Supprimer un sommet, c’est facile aussi : on choisit un sommet, on le supprime, et on supprime aussi tous les arcs qui y sont reliés, parce que sinon on sait pas où ils vont de toute façon. La notion de contraction est un tout petit peu plus sioux. L’idée, c’est qu’on prend deux sommets reliés par un arc, et qu’on les transforme en un seul sommet. Le sommet résultant est attaché à tous les arcs qui étaient dans le graphe précédent. On peut imaginer qu’on « pince » deux sommets qui se rapprochent, qui se rapprochent, qui se rapprochent et POUF qui n’en font plus qu’un. Un petit exemple, dans lequel je contracte l’arc rouge et dans lequel j’obtiens le sommet rouge :

contraction

Donc, en gros, ce que Wagner dit, c’est que « si je bricole mon graphe un peu et que j’arrive à faire apparaître K_5 ou K_{3,3}, alors je ne peux pas dessiner le graphe sans croisement. Par contre, si je ne peux pas faire apparaître K_5 ou K_{3,3}, alors je peux dessiner le graphe sans croisement. »

Il se trouve qu’il existe un théorème qui généralise cette idée de « mineurs exclus » – c’est un théorème de Robertson et Seymour dont la preuve prend… 20 articles, publiés de 1983 à 2004. Le théorème s’énonce comme suit :

Toute famille de graphe fermée pour les mineurs peut être décrite par un ensemble fini de mineurs exclus.

Explications : une famille de graphes fermée pour les mineurs, c’est un ensemble de graphes tels que, si je prends un graphe quelconque de cet ensemble, que j’en prends un mineur (avec la définition précédemment donnée), alors le mineur est aussi dans la famille en question. Ce que Robertson et Seymour disent, c’est que dans une famille comme ça, il existe un ensemble fini de mineurs exclus, c’est-à-dire que si on trouve ce mineur dans un graphe, alors le graphe ne fait pas partie de la famille.

Appliquons ça à l’exemple des graphes planaires. Les graphes planaires sont une famille de graphes fermée pour les mineurs : si je prends un mineur d’un graphe planaire, je peux toujours dessiner le mineur en question dans le plan sans avoir de croisement d’arc. Et les mineurs exclus sont K_5 et K_{3,3} : si je trouve ces mineurs dans le graphe, le graphe n’est pas planaire. Wagner est plus « puissant » que Robertson & Seymour pour les graphes planaires, parce qu’il donne les mineurs exclus explicitement.

Là où ça devient drôle, c’est qu’en général, on ne connaît pas les mineurs exclus en question. On sait qu’ils existe, on sait qu’il y en a un nombre fini, mais on ne sait pas quelle tête ils ont. Un petit exemple pour terminer : supposons que je veuille dessiner mon graphe non pas sur une feuille de papier, mais sur un tore – un donut, si ça vous parle plus.

donutL’idée, ça serait que je dessine des points sur mon donut, et que je les relie avec des arcs, exactement comme je le fais dans le plan. Si je fais ça, et que j’arrive à dessiner mon graphe sans croiser d’arcs, j’ai un graphe non pas planaire, mais toroïdal (ou donutidal, si vous voulez). La famille des graphes toroïdaux est fermée pour les mineurs, donc il existe une famille de mineurs exclus pour cette famille. Jusqu’à présent, on en a trouvé plus de 16 000. Et on ne sait pas combien il y en a au total. Amusant, non ?

(Et si vous voulez essayer de tous les trouver, je crois qu’il faut commencer par faire des donuts 😉 )

Introduction : Théorème à périodicité aléatoire – TPA

Publié le par Balise3 commentaires

Hoplà,

J’ai toujours dans l’idée de faire un billet ou deux ou 12 sur les algos aléatoires, mais comme c’est long et que j’ai pas encore décidé par où attaquer, je vais faire d’autres trucs en attendant, parce que bon, ya pas de raison.

J’introduis donc aujourd’hui une série de Théorèmes à Périodicité Aléatoire, ou TPA – des billets que je vais essayer de faire courts, mais à dates aléatoires (je tiens pas à faire « le théorème de la semaine », ça risque de durer 3 semaines et encore…), présentant un résultat rigolo, éventuellement des éléments de preuve si elle tient dans la contrainte « billet court », probablement majoritairement dans le domaine informatique théorique / combinatoire, mais sait-on jamais, je vais peut-être me retrouver à diverger à un moment…

Ceci est un billet d’annonce – un vrai billet avec un vrai théorème devrait apparaître ici cet après-midi ou demain. Spoiler : ça va parler de graphes.

« Le méta pue », ou Crédibilité des preuves

Publié le par Balise1 commentaire

Il y a quelque temps, une soumission à arXiv a fait pas mal de bruit. arXiv, pour ceux qui ne connaissent pas, est une archive d’articles scientifiques – les auteurs y soumettent en général des versions préliminaires d’articles publiés ailleurs. arXiv fait un peu de modération pour éviter le spam et les trucs vraiment délirants, mais, si je comprends bien, tant que ça a à peu près une tronche d’article scientifique dans les domaines gérés par arXiv, ça passe la modération.

Et, donc, le 26 mai, ya un article intitulé A Polynomial Time Algorithm for the Hamilton Circuit Problem, par Xinwen Jiang, qui est apparu sur arXiv. Dans la description de l’article, il y a une petite phrase : « Our result implies NP=P », c’est à dire « Notre résultat implique que P=NP ». Pour un petit rappel sur le problème en question, il se trouve que j’ai causé à ce sujet dans le billet intitulé, fort logiquement, Le problème « P est-il égal à NP ? ».

J’avoue que je ne comprends pas bien pourquoi, spécifiquement, ce papier a fait du bruit. Et par « faire du bruit », j’entends qu’il est passé plusieurs fois sur mon radar, par plusieurs sources différentes. Je ne comprends pas pourquoi, parce que des papiers qui prouvent que P = NP ou que P ≠ NP, il y en a au moins une dizaine par an – voir par exemple The P-versus-NP Page qui vise à tous les recenser. Et qu’on ne fait pas tout un pataquès tous les mois à ce sujet.

C’est bizarre, parce qu’il y a tout un tas de choses qui font que ce papier est peu crédible. Scott Aaronson a écrit des choses sur la crédibilité des articles scientifiques « révolutionnaires » : je citerai ici Ten Signs a Claimed Mathematical Breakthrough is Wrong et Eight Signs A Claimed P is not NP Proof Is Wrong. Aaronson s’intéresse plutôt aux preuves P ≠ NP, mais certains arguments sont aussi valides dans le cas des preuves P = NP.

J’avoue humblement que je n’ai pas lu le papier de Xinwen Jiang. Je ne sais pas non plus si quelqu’un (n’importe qui) a lu le papier de façon sérieuse. Je n’ai trouvé aucun article ou billet de blog disant « la preuve de Xinwen Jiang est fausse et voici pourquoi », ni d’article « meeeeerde, ça marche, son truc ». La discussion la plus fournie que j’ai vu passer est celle de Hacker News dans ce fil de discussion.

Personnellement, la raison principale pour laquelle j’ai abandonné la lecture du papier va sembler extrêmement snob. Mais le papier n’est pas écrit en \LaTeX. Du coup… ben j’ai pas eu le courage, bêtement. La mise en page est immonde, les maths sont illisibles. Je regarde ce truc et j’ai mal au crâne. Un petit morceau de moi se dit que si le type en face n’a pas pris la peine de faire en sorte que son machin soit lisible, je vois pas pourquoi je prendrais la peine de tenter de le lire. Évidemment, c’est hyper-fallacieux, comme argument. Parce que si jamais quelqu’un arrive avec une preuve qui marche, il a moyen de troller une communauté complète rien qu’en publiant sa preuve en Word 😀 Après, je peux argumenter sur le fait que j’ai jamais réussi à utiliser l’éditeur d’équations de Word de façon raisonnablement déterministe, alors que \LaTeX se comporte plutôt mieux de ce point de vue, et que j’ai donc plus confiance dans le fait qu’un papier en \LaTeX reflète effectivement ce que l’auteur voulait dire. Mais ça touche probablement à la mauvaise foi aussi.

Dans les arguments un demi-chouille plus « sérieux », mais qui touchent toujours au méta : l’auteur est tout seul, et il ne remercie aucun collègue, aucun relecteur. Sur un résultat de cette ampleur, c’est un peu bizarre. Évidemment, le concept de génie solitaire qui résout tout seul un problème qui a échappé à des milliers de chercheurs est extrêmement romantique. Mais il est aussi extrêmement peu crédible.

Troisième point : les références bibliographiques. Il y a 12 références bibliographiques dans cet article. Dix d’entre elles sont des auto-références (l’auteur fait référence à des travaux personnels précédents). La première de la liste est un bouquin très classique, genre bouquin de cours sur le sujet. Là encore, c’est douteux.

Pour finir, l’article se termine par « Until now, since 2010.10.06, more than 52 millions of instances have been generated randomly, each of which has 100 vertices. Some instances contain a simple path while others (it is the majority in all the generated instances) do not. All the results show that our polynomial time algorithm can get the same answer as the backtracking algorithm does. No exception. », ce qui se traduit par « Jusqu’à présent, depuis le 6 juin 2010, nous avons généré aléatoirement plus de 52 millions d’instances sur 100 sommets chacunes. Certaines instances contiennent un chemin simple tandis que d’autres (la majorité des instances générées) non. Tous les résultats montrent que notre algorithme polynomial ont le même résultat que l’algorithme de backtracking. Aucune exception. ». Ça pourrait sembler être un argument en faveur de la preuve. Mais il y a plusieurs choses qui sont discutables sur cet argument. Déjà, il se peut que le générateur aléatoire d’instances soit biaisé, et se trouve louper les instances pour lesquelles ça ne marche pas. D’autre part, le nombre de sommets considéré est relativement bas. Si ça se trouve, ça plante pour 1000 sommets. Ou pour 101. Tertio, il se peut que les instances « difficiles » du problème soient rares. Ça fait partie des choses qu’on ne sait pas, d’ailleurs : si P ≠ NP, les instances d’un problème NP donné pour lesquelles c’est effectivement un facteur (c’est-à-dire qui n’ont pas de caractéristique permettant de résoudre l’instance par un algorithme rapide) sont-elles rares ou fréquentes ? Quatro, l’argument « ça fait un moment que je cherche et j’ai toujours pas trouvé de truc qui fait que ça marche pas »… j’ai essayé, hein, ben souvent les gens qui corrigent mes copies sont pas pour 😀

Bref, comme dit précédemment, c’est un peu des arguments fallacieux, tout ça, parce que ça serait facile de transformer n’importe quel papier « crédible » en papier « absolument pas crédible », et là j’aurai l’air très très bête. Je ne sais pas exactement ce que je veux dire, en fait. Dans un sens, ça me gène de recourir à ce genre d’argument pour décider que « ça sent pas bon, son truc », parce qu’il y a toujours le doute, dans un coin de neurone, du « oui, mais si les apparences étaient trompeuses ? ». D’un autre côté, comme dit Aaronson, il y a suffisamment de papiers sur le sujet pour que des heuristiques de crédibilité soient nécessaires. Quelque part, c’est peut-être à relier au processus de recrutement d’un candidat. Un candidat à un job doit souvent passer par des « formes obligées » qui démontrent sa crédibilité. Et il y a probablement un certain nombre de « faux négatifs » dans tout ce processus de formes obligées. On peut le déplorer. Et, dans le cas d’une preuve P = NP, un faux négatif serait… intéressant 😀

Mais dans le cas d’une preuve P = NP, je soupçonne qu’il faille redoubler d’attention à la crédibilité du papier. L’immense majorité de la communauté scientifique est raisonnablement convaincue que P ≠ NP. Du coup, arriver en affirmant l’inverse… ben ça part pas bien, déjà. Et si « le méta pue », il y a peu de chance que quiconque prenne la peine d’examiner le papier.

Et peut-être que demain je vais me prendre une grosse baffe dans la figure parce qu’un papier dont « le méta pue » va démontrer correctement un résultat que personne n’attend. Je crois que P ≠ NP. Et quand je dis « je crois », c’est vraiment exactement ça : une croyance, peut-être même une foi. N’empêche que j’adorerais avoir tort. Ça serait profondément drôle.. Si ça se trouve, on va trouver demain un algorithme pour SAT en n¹⁰⁰⁰⁰. Ben on sera bien avancés avec ça. Les années qui suivront seraient probablement super marrantes – parce que probablement on se tirerait tous la bourre pour faire descendre ce fichu 10000, et ça finirait probablement par arriver. Ça serait marrant.

Probabilités – Partie 2

Publié le par Balise2 commentaires

This post was translated to English here: Intro to probability theory – part 2.

Bon. Donc, je vous ai lâchement abandonnés après une première partie sur les probabilités, et puis ça fait un peu trois mois. Mes excuses. On va quand même reprendre comme si de rien n’était, parce que c’est mon blog et que je fais ce que je veux.

Donc, aujourd’hui, c’est raviolisvariables aléatoires. Le concept des variables aléatoires, c’est de réussir à faire des trucs qui se tiennent à peu près quand on ne sait pas exactement ce qui se passe (par exemple on jette un dé) – mais qu’on veut quand même avoir une idée de ce qui peut se passer. Dans le cas d’un seul dé, c’est peut-être un peu overkill, mais gardons les exemples simples pour l’instant.

L’idée, c’est qu’on prend une variable, mettons X, et qu’on considère toutes les valeurs qu’elle peut avoir, avec la probabilité associée. Pour reprendre les exemples de la partie 1, on peut par exemple définir une variable aléatoire sur la valeur d’un dé à six faces, et appeler ça X. Pour que ma définition soit complète, il faut que j’énonce toutes les valeurs possibles de X : si j’ai un dé à 6 faces, ben ça sera les valeurs de 1 à 6, et il faut que je dise quelle probabilité a chaque valeur : pour un dé non pipé, toutes ces probabilités sont égales à 1/6. On peut écrire ça rapidement comme ça :

\forall i \in \{1,2,3,4,5,6\}, \Pr[X = i] = \frac 1 6

Ça se lit « Pour tout élément i de l’ensemble {1,2,3,4,5,6}, la probabilité que X soit égal à i est égale à 1/6 ». On dit aussi que l’ensemble des valeurs qu’une variable aléatoire X est le domaine de X.

Un truc qu’on fait très, très souvent avec des variables aléatoires, c’est de calculer leur espérance. L’espérance d’une variable aléatoire, on peut voir ça comme sa valeur moyenne, ou comme un « si je lance mon dé 1000 fois, et que je fais la moyenne de tous mes résultats (somme des résultats divisée par 1000), qu’est-ce que je m’attends à avoir comme nombre ? ». Notons que l’explication que je donne là n’est pas très rigoureuse, mais j’espère qu’elle donne une idée de la chose.

Il se trouve qu’on peut calculer cette espérance (notée E[X]) de façon assez simple avec la formule suivante :

E[X] = \sum_{i} \Pr[X = i] \times i

ce qui se lit « somme pour tous les éléments i de i fois la probabilité que X soit égal à i ». Bon, ma définition n’est pas tout à fait correcte, parce que je ne définis pas ce sur quoi la somme se fait exactement. Pour corriger ça, je m’en vais faire ça de ce pas : je fais la somme sur tout le domaine de X. On va prendre un exemple, parce que je sens que ça va aider. Si je reprends mon exemple précédent avec mon dé, le domaine c’est {1,2,3,4,5,6}, donc j’ai

E[X] = \sum_{i = 1}^6 \Pr[X = i] \times i

et ça je peux l’étendre comme ça :

E[X] = 1 \times \Pr[X = 1] + 2 \times \Pr[X = 2] + 3 \times \Pr[X = 3] + 4 \times \Pr[X = 4] + 5 \times \Pr[X = 5] + 6 \times \Pr[X = 6]

Comme, dans le cas de mon dé, toutes les probabilités sont égales à 1/6, je conclus par

E[X] = \frac 1 6 \times (1 + 2 + 3 + 4 + 5 + 6) = \frac{21}{6} = 3.5

Bon, maintenant, on va prendre un exemple un peu plus compliqué. Supposons que je lance n dés, et que je m’intéresse au nombre de 6 qu’il y a dans mes n dés. Déjà, je vous pose la question : d’après vous, si je lance n dés, combien de 6 y aura-t-il ? Évidemment, c’est difficile de répondre exactement. Par contre, on peut se dire qu’il n’y a pas vraiment de raison qu’il y ait plus ou moins de 6 que de 1, de 2, de 3, de 4 ou de 5, et que globalement les dés devraient se répartir à peu près équitablement dans les 6 nombres, et que donc il y aurait à peu près 1/6 n six sur mes n dés. (Bon, sauf quand on joue les orks à Warhammer 40k, là il y a à peu près 3 six sur 140 dés). Donc, on va essayer de prouver ça un peu proprement.

Donc, je définis Y comme la variable aléatoire « nombre de six sur n dés ». Et là, ben on est bien avancés. Le domaine de Y, c’est tous les nombres de 0 à n. Je peux réussir à trouver la probabilité d’avoir, par exemple, exactement 3 dés avec la valeur 6 sur mes n dés, et même une formule générale pour k dés, mais faire la somme de tout ça, ben j’ai un peu la flemme. Alors, je vais ruser.

Ya un truc super pratique qui s’appelle la linéarité de l’espérance qui dit que l’espérance de la somme de plusieurs variables est égale à la somme de l’espérance des variables en question. En plus compact :

E[A + B] = E[A] + E[B]

Ça, c’est vrai pour toutes les variables aléatoires A et B. Par contre, attention, c’est assez spécifique à l’addition en général. Par exemple, on ne peut pas, en général, dire que E[A \times B] = E[A] \times E[B] – c’est vrai, en particulier, si les variables aléatoires A et B sont indépendantes, mais ce n’est pas vrai en général. Fin de l’aparté.

Et donc, la ruse, là, c’est de définir n variables, qu’on va appeler Y_1, Y_2, ..., Y_n, et on va se débrouiller pour que la variable Y soit la somme de toutes ces variables. Et pour ça, on définit chaque variable Y_1 comme suit : elle a pour domaine {0,1} (c’est-à-dire qu’elle ne peut prendre que la valeur 0 ou 1), et elle a la valeur 1 exactement lorsque le dé numéro 1 a la valeur 6. On définit les valeurs suivantes de la même manière. Puisque j’ai n variables, et qu’elles ont la valeur 1 quand le dé qui leur correspond vaut 6, je peux écrire que

Y = \sum_{i = 1}^{n} Y_i

Et, par linéarité de l’espérance, du coup, j’ai

E[Y] = E[\sum_{i=1}^n Y_i] = \sum_{i=1}^n E[Y_i]

L’astuce, c’est que mes variables Y_i, elles sont vachement plus simples. Avec une probabilité 1/6, elles ont la valeur 1, et avec une probabilité 5/6, elles ont la valeur 0 (puisqu’avec une probabilité 1/6, le dé i a la valeur 6). Du coup, l’espérance de Y_i, elle est aussi vachement plus simple à calculer :

E[Y_i] = 1 \times \frac 1 6 + 0 \times \frac 5 6 = \frac 1 6

et ça, ben ça me donne directement l’espérance de Y :

E[Y] = \sum_{i=1}^n E[Y_i] = \sum_{i=1}^n \frac 1 6 = \frac 1 6 n

comme intuité au départ. Fou, non ?

Bon, évidemment, mes exemples là sont plutôt simples. Mais on peut utiliser le même genre d’outils dans des cas beaucoup plus compliqués. Et il existe tout un tas d’autres outils qui permettent d’évaluer des choses autour de variables aléatoires, et d’avoir une assez bonne idée de ce qui se passe, même quand on jette des dés. Il est probable que j’y revienne si/quand j’en aurai besoin, mais les bases sont là ! Des questions ? 🙂

Probabilités – partie 1

Publié le par Balise12 commentaires

This blog post has been translated to English here: Intro to probability theory – part 1

Pouf pouf. Donc, j’ai trois personnes qui ont répondu à mon petit sondage et je les remercie. Yoogx m’a réclamé des algos aléatoires, donc je vais faire des algos aléatoires, mais avant je vais faire un peu de probas, histoire d’être sûre que tout le monde parle de la même chose. Évidemment, pour ledit Yoogx, ça va probablement pas être super utile ce que je raconte, mais espérons qu’il n’y aura pas que lui que la question des algos aléatoires intéresse, et sinon il est encore temps de s’exprimer 😉

Bon, donc, les probas. Les probas, c’est un peu pénible, parce que c’est des trucs qu’on utilise relativement souvent dans la vie… j’ai envie de dire « quotidienne », ça serait peut-être un peu exagéré, et en même temps ça arrive a être étonnamment contre-intuitif quand ça s’y met. Ça, ou alors l’être humain est nul en probas, ce qui est possible aussi.

J’ai pas super envie de définir formellement le concept de probabilité (« étant donné un univers \Omega, des événements blah…. » ouais, bon, vraiment pas envie), ce que je vais probablement regretter, mais on va essayer de rester sur les démos « avec les mains » (mais correctes, parce que bon). Et je vais espérer que ce que je raconte va rester suffisamment simple pour pouvoir me passer du formalisme en question. Sinon on verra 😛

Je suppose, pour éviter les petits malins, que je suis dans des conditions « correctes » : mon dé n’est pas pipé, ma pièce est une vraie pièce, etc.

On commence classique. Je lance une pièce, quelle est la probabilité qu’elle tombe sur le côté pile ? La réponse est 1/2 ; j’ai deux événements possibles (la pièce peut tomber côté pile ou côté face), et ils ont tous les deux la même probabilité de se produire. Idem si je lance un dé à six faces : la probabilité qu’il fasse un 4 est 1/6 ; j’ai six événements possibles qui ont tous la même probabilité de se produire. De manière générale, je vais me permettre de dire que si je fais une expérience (lancer un dé, lancer une pièce) qui a k résultats possibles, et que tous ces résultats possibles ont la même probabilité (« chance d’arriver »), alors la probabilité de chacun de ces résultats est 1/k.

Il se peut que tous les événements n’aient pas la même probabilité, mais il y a quelques règles immuables. Une probabilité est toujours comprise entre 0 et 1. Un événement qui n’arrive jamais a une probabilité 0 ; un événement qui arrive toujours a une probabilité 1. Si quelqu’un met dans mon porte-monnaie une pièce qui n’a que deux côté pile, si je la lance, elle tombe côté pile avec une probabilité 1 et côté face avec une probabilité 0. D’autre part, la somme de toutes les probabilités de tous les événements possibles de mon expérience est égale à 1. Dans le cas où j’ai k événements qui ont la même probabilité, ça fait effectivement k*1/k = 1. Si j’ai un dé qui a trois faces 1, 2 faces 2 et une face 3, la probabilité qu’il fasse 1 est 3/6 = 1/2, la probabilité qu’il fasse 2 est 2/6 = 1/3 et la probabilité qu’il fasse 3 est 1/6 ; la somme est 1/2 + 1/3 + 1/6 = 1.

Bon, maintenant, les trucs auxquels il faut faire un peu attention. Quelle est la probabilité que le dé (à six faces, normal) fasse 3 ou 5 ? Facile : la probabilité qu’il fasse 3, c’est 1/6, la probabilité qu’il fasse 5, c’est 1/6, 1/6+1/6 = 1/3. Ça, ça marche si les événements sont disjoints, c’est à dire si quand l’un est vrai, l’autre ne peut pas l’être : si j’ai fait un 5, alors je ne peux pas avoir fait un 3, et vice versa.

Ça ne marche pas si les événements peuvent se produire en même temps. Par exemple, je lance une pièce et un dé, et je m’intéresse à la probabilité que la pièce tombe sur pile, ou que le dé tombe sur 6. Je ne peux PAS dire que c’est égal à la probabilité que la pièce tombe sur pile (1/2), plus la probabilité que le dé tombe sur 6 (1/6), pour un total de 2/3. Une manière de voir ça, c’est de modifier un peu l’expérience pour voir que ça ne marche pas à tous les coups. Par exemple, la probabilité que le dé fasse 1, 2, 3 ou 4 est de 4/6 = 2/3. La probabilité que la pièce fasse pile est de 1/2. Ce n’est pas possible que la probabilité que l’un ou l’autre arrive fasse la somme de ces deux probabilités = 2/3 + 1/2 = 7/6… ce qui est supérieur à 1 ! (Et une probabilité est toujours inférieure ou égale à 1).

Un truc qui est toujours vrai, par contre, c’est que si j’ai deux événements A et B, alors

\Pr(A \cup B) \leq \Pr(A) + \Pr(B)

c’est à dire que la probabilité de l’union de deux événements (événement A ou événement B) est toujours inférieure à la somme de la probabilité des deux événements. On peut étendre ça à plusieurs événements : la probabilité de l’union de plusieurs événements est inférieure à la somme de la probabilité de tous les événements. Ça peut paraître tout con et pas très intéressant, mais en pratique c’est très utilisé. En anglais, ça s’appelle l’union bound (la « borne de l’union » ?), en français l’inégalité de Boole. Cette inégalité n’est pas toujours très utile. Dans le cas « mon dé fait 1, 2, 3 ou 4, ou ma pièce fait pile », elle borne la probabilité à 7/6… ce qu’on savait déjà, puisque 7/6 est plus grand que 1. Elle est déjà un peu plus utile pour borner la probabilité que le dé fasse 6 ou que la pièce tombe sur pile, on sait que cette probabilité est inférieure à 2/3. En pratique, dans le contexte des algorithmes aléatoires, elle est très utilisée : les probabilités qu’on considère sont toutes petites, et on peut en ajouter beaucoup avant que la borne n’ait plus de sens. Elle n’est pas toujours suffisante non plus, mais c’est un outil à garder précieusement.

Dans le cas qui nous intéresse ici, cependant, l’outil le plus utile c’est le principe d’inclusion-exclusion. Pour deux événements A et B, il s’énonce comme ça :

\Pr(A \cup B) = \Pr(A) + \Pr(B) - \Pr(A \cap B)

c’est-à-dire que la probabilité que l’événement A ou l’événement B arrive est égal à la somme des probabilités des deux événements, moins la probabilité que les deux événements arrivent en même temps. L’idée, c’est que si les deux événements peuvent arriver en même temps, on compte cette probabilité là « deux fois » si on fait la somme. Ça se voit sans doute mieux avec des patates (diagramme de Venn, on dit, quand on est distingué) :

patates

Si je considère tout ce qui est contenu dans le hachuré vert, et tout ce qui est contenu dans le hachuré rose, je compte deux fois ce qui est hachuré vert et hachuré rose, donc je retire une fois ce qui est hachuré vert et hachuré rose pour retomber sur mes pattes.

Bon, évidemment, ça pose la question de savoir comment calculer la probabilité que deux événements arrivent. Il y a le cas facile, et le cas compliqué. Dans le cas facile, les événements sont dits indépendants : la probabilité de l’un n’a aucune influence sur la probabilité de l’autre. C’est une notion qui est à peu près claire (bien que pas forcément intuitive) si on considère des dés et des pièces, mais c’est une notion à laquelle il faut généralement faire super attention quand on veut l’appliquer. Prouver que deux événements sont indépendants peut s’avérer compliqué, et s’en sortir quand ils ne le sont pas… aussi.

Quand deux événements sont indépendants, on a

\Pr(A \cap B) = \Pr(A) \times \Pr(B)

c’est-à-dire que la probabilité que les deux événements arrivent est égale au produit de la probabilité des deux événements. Si je lance une pièce et un dé, le fait que la pièce tombe sur pile et le fait que le dé fasse 6 sont indépendants : l’un n’a aucune influence sur l’autre. La probabilité que les deux arrivent est donc 1/2 × 1/6 = 1/12. Remarquons que cette probabilité conjointe est plus petite que 1/2 et plus petite que 1/6. C’est « évident » au sens où une probabilité est inférieure à 1, et donc quand on multiplie deux probabilités entre elles le résultat est inférieur aux deux. Une autre manière de voir ça c’est que le fait que les deux événements indépendants se produisent, ben c’est moins probable que le fait que seulement l’un des deux se produise.

Pour des exemples d’événements qui ne sont pas indépendants, on peut par exemple considérer l’événement A « le dé fait 1 » et l’événement B « le dé fait un nombre impair ». Dans ce cas là, les deux événements ne sont pas indépendants, puisque si le dé fait 1, alors le dé fait un nombre impair ; et si le dé fait 2, alors il ne peut pas faire un nombre impair en même temps. Dans ce cas précis, l’événement A est inclus dans l’événement B, donc c’est facile : l’intersection des deux événements, c’est l’événement le plus petit : l’événement A \cap B est égal à l’événement A. On peut faire des trucs plus subtils ; par exemple on peut définir pour l’événement A « le dé fait 1, 4 ou 6 » et garder l’événement B « le dé fait un nombre impair », auquel cas les deux événements ne sont pas non plus indépendants. La probabilité que A et B soient valides correspond exactement à la probabilité que le dé fasse 1 (parce que c’est le seul cas qui soit à la fois dans l’ensemble {1, 4, 6} et impair), c’est à dire 1/6 ; si on multiplie les probabilités de A (1/2) et de B (1/2) sans faire plus attention que ça, on a 1/4 et on s’est vautré.

Bon, et maintenant, une dernière pour la route : il me reste à parler de probabilités conditionnelles. Les probabilités conditionnelles, c’est justement une manière de gérer les dépendances entre des événements. On note les probabilités conditionnelles Pr(A | B), et on lit ça « probabilité de A sachant B », et on comprend ça comme « probabilité de A sachant que B arrive/est arrivé ». Si A et B sont indépendants, alors Pr(A | B) = Pr(A) – savoir que B se passe n’a aucune influence sur la probabilité de A. Pour le cas précédent, où A est l’événement « le dé fait 1 » et B est l’événement « le dé fait un nombre impair », on peut voir le « sachant B » comme une restriction de l’ensemble des événements possibles. Le dé a fait un nombre impair, on le sait ; avec la même probabilité il a donc fait 1, 3 ou 5, mais la probabilité, sachant qu’il ait fait un nombre impair, qu’il ait fait 2, 4 ou 6 est 0. Donc on a Pr(A | B) = 1/3.

Il y a une formule « générale » pour les probabilités conditionnelles :

\Pr(A \mid B) = \frac{\Pr(A \cap B)}{\Pr(B)}

On peut re-dériver, à partir de cette formule, le fait que si A et B sont indépendants, alors Pr(A | B) = Pr(A), parce qu’alors

\Pr(A \mid B) = \frac{\Pr(A) \times \Pr(B)}{\Pr(B)} = \Pr(A)

Elle est aussi très utilisée dans l’autre sens :

\Pr(A \cap B) = \Pr(A \mid B) \times \Pr(B) = \Pr(B \mid A) \times \Pr(A)

parce qu’il arrive qu’il soit plus facile de comprendre ce qu’il se passe dans le contexte des probabilités conditionnelles que dans le contexte de deux événements qui arrivent en même temps de façon non indépendante. Et il faudrait techniquement que je parle de la loi des probabilités totales ici, mais je crois que ça va allonger un peu trop un billet qui est déjà pas court, donc je ferai ça plus tard.

Dans le billet prochain, on parlera de variables aléatoires, parce que c’est pareil, ça va pas rentrer dans un billet de taille raisonnable d’en parler ici 🙂

Problèmes NP-complets

Publié le par Balise5 commentaires

Dans un billet précédent, j’ai tenté d’expliquer avec brio (je vous laisse choisir le verbe qualifié par « avec brio ») le problème « P = NP ». J’y ai donné une définition de la classe NP, que je répète ici : NP est la classe des problèmes pour lesquels, pour chaque instance de type « oui », on peut me convaincre en temps polynomial que la réponse est « oui » en me fournissant une preuve que c’est effectivement le cas. Et en fin de billet, j’ai vaguement mentionné la notion de problème NP-complet.

La définition usuelle de problème NP-complet, c’est un problème qui est « dans NP » et « NP-difficile ». Je vais donc expliquer ce que veut dire NP-difficile 🙂 De façon informelle, c’est un problème qui est au moins aussi difficile que tous les problèmes de la classe NP. Une autre façon informelle de dire ça, c’est qu’il est aussi difficile qu’un autre problème NP-difficile. Le problème de cette définition, c’est qu’il faut bien commencer quelque part, et avoir un premier problème NP-difficile pour le comparer aux autres.

L’archétype des problèmes NP-difficiles (et donc NP-complets, parce que SAT est dans NP), c’est le problème SAT, dont j’ai parlé dans le billet précédent. C’est pas évident, a priori, que SAT est NP-difficile. Mais on peut montrer que même 3-SAT est NP-difficile : 3-SAT représente les instances de SAT où toutes les clauses ont exactement trois littéraux ((Les avis diffèrent sur la terminologie exacte. De nombreux auteurs définissent 3-SAT comme les instances de SAT où toutes les clauses ont au plus deux littéraux. J’appelle ça (sur la suggestion de mon prof de SAT) <=3-SAT. Dans le cas présent ça m’arrange de définir sur exactement 3 littéraux, donc je fais ça, OK ?)). Je ne vais en pas expliquer la preuve, parce que ça impliquerait que je passe pas mal de temps à expliquer des choses que j’ai pas fondamentalement envie d’expliquer. Pour les gens intéressés par la question, ça a été démontré en 1971 et c’est connu sous le nom de Théorème de Cook-Levin.

Maintenant qu’on en a un, on peut en trouver d’autres par réduction. On réduit un problème NP-difficile (par exemple SAT) à un autre problème qu’on veut prouver NP-difficile, appelons le A. Pour faire ça, on démontre que si on peut résoudre A efficacement, c’est-à-dire en temps polynomial, alors on peut résoudre SAT efficacement.

L’idée générale de ce genre de preuve, c’est qu’on prend une instance quelconque du problème NP-difficile, et on la transforme, en temps polynomial, en instance du problème A qui permette de conclure sur l’instance originale. Maintenant, supposons qu’on sache résoudre le problème A (c’est-à-dire n’importe quelle instance du problème A) en temps polynomial. Alors on peut prendre n’importe quelle instance de SAT, la transformer en une instance du problème A, résoudre l’instance du problème A, et conclure. La transformation se fait en temps polynomial, la résolution de A se fait en temps polynomial, la somme des deux est polynomiale, donc on sait résoudre n’importe quelle instance de SAT en temps polynomial, donc on sait résoudre SAT en temps polynomial. Facile.

Les problèmes NP-complets sont donc, en quelque sorte, « équivalents » en terme de complexité : si on sait en résoudre un en temps polynomial, alors on peut résoudre tous les autres en temps polynomial aussi, et on peut résoudre tous les problèmes de NP en temps polynomial (puisqu’ils sont aussi difficiles que tous les problèmes de la classe NP). Donc, si on trouve un moyen de résoudre en temps polynomial toutes les instances d’un problème NP-complet… on a démontré que P = NP. Et gagné un million de dollars. Et surpris beaucoup, beaucoup de monde.

Il y a toute une série de problèmes pour lesquels on sait qu’ils sont NP-difficiles, ou NP-complets si en plus ils sont dans NP. Il y a des gens qui s’intéressent à des problèmes… exotiques, dirons-nous ; je vais juste laisser quelques liens pour les gens intéressés et que ça fera rigoler :

Passé cet interlude amusant, je vais donner un exemple de réduction pour prouver que le problème CLIQUE est NP-complet. C’est probablement l’exemple bateau que tout le monde donne quand il parle de ce genre de chose, mais il doit y avoir une raison à ça (la raison en est que le problème est raisonnablement facile à décrire et que la réduction est relativement simple par rapport à ce qu’on peut voir ailleurs). Le truc que j’explique ici est largement repompé du CLRS, c’est-à-dire le Cormen, Leiserson, Rivest & Stein, c’est-à-dire Introduction to Algorithms, traduit en français sous le nom Algorithmique (je ne sais pas ce que vaut cette traduction) – c’est le bouquin de référence de BEAUCOUP de cours d’algorithmique.

Donc, le problème CLIQUE est le suivant : étant donné un graphe (un ensemble de sommets et d’arcs) G, contient-il une clique de taille k ? Une clique de taille k, c’est un ensemble de k sommets qui sont tous reliés les uns aux autres. Par exemple (vous m’excuserez, je recycle mes figures), ce machin-là est est une clique de taille 8. Notons au passage qu’il contient également une clique de taille 1 (un seul sommet), 2 (un arc), 3 (un triangle), 4, 5, 6 et 7, puisqu’on peut trouver des ensembles de sommets de cette taille qui sont tous reliés les uns aux autres.

8clique

On veut réduire 3-SAT à ce problème ; comme 3-SAT est NP-difficile, CLIQUE est NP-difficile aussi. CLIQUE est dans NP, parce que si je donne k sommets, c’est facile de vérifier que ces k sommets sont effectivement tous reliés les uns aux autres. Donc, si CLIQUE est NP-difficile, CLIQUE est NP-complet.

Pour attaquer ma réduction, je prends une formule 3-SAT. Je prends une formule 3-SAT CNF (j’ai expliqué ce que ça veut dire dans mon article sur SAT), c’est-à-dire une formule qui a cette tête là :

(x_1 \vee x_2 \vee x_3) \wedge (\bar x_2 \vee x_4 \vee \bar x_5) \wedge (x_1 \vee \bar x_2 \vee \bar x_3) \wedge ...

c’est-à-dire un ensemble de m clauses composées d’au plus 3 littéraux reliés par des OU, et les clauses étant reliées par des ET.

À partir de là, on crée un graphe contenant 3*m sommets. Chacun de ces sommets correspond à un littéral de la formule, éventuellement dupliqué. Pour visualiser les choses plus facilement, ça peut peut-être aider de grouper les sommets en groupes de trois. Dans l’exemple de la formule ci-dessus, ça donne les sommets suivants :

x_1, x_2, x_3~;\bar x_2, x_4, \bar x_5~; x_1, \bar x_2, \bar x_3

Ensuite, on ajoute des arcs partout. Enfin, presque partout. On n’ajoute pas d’arcs dans les « groupes » correspondant aux clauses. On n’ajoute pas non plus d’arcs entre les littéraux qui ne sont pas « compatibles », c’est-à-dire l’inverse l’un de l’autre. Si j’ai deux littéraux x_1 et \bar x_1, je ne crée pas d’arc entre eux. Pour ma mini-formule au-dessus, voilà ce que donne le graphe en question :

clique3sat1

et voilà les arcs qui ne sont PAS dans le graphe précédent :

clique3sat2

Et maintenant qu’on a ce graphe là, l’idée, c’est que la formule SAT peut être satisfaite si et seulement si le graphe (le premier) a une clique de taille m (m étant le nombre de clauses de la formule SAT). J’ai donc deux choses à prouver :

  • si la formule peut être satisfaite, alors le graphe a une clique de taille m
  • si le graphe a une clique de taille m, la formule peut être satisfaite.

On va commencer par le premier point. Supposons que la formule puisse être satisfaite. Donc, on peut affecter une valeur à toutes les variables de sorte que la formule soit satisfaite. Par conséquent, toutes les clauses peuvent être satisfaites par cette affectation. Donc, dans chaque clause, il existe un littéral qui a pour valeur 1 (le littéral « positif », par exemple x_1 si la variable a la valeur 1, le littéral « négatif », par exemple \bar x_1 si la variable a la valeur 0). On considère, dans chaque « groupe » de sommets du graphe défini précédemment, le sommet correspondant à ce littéral (si plusieurs littéraux ont la valeur 1, on en prend un au pif). Comme on prend un sommet par groupe, et qu’on a m groupes, on arrive à m sommets. On veut maintenant montrer qu’il y a un arc entre toutes les paires de sommets de cet ensemble de sommets. Or, les deux raisons pour lesquelles on pourrait ne pas en avoir, c’est soit que les sommets sont dans le même groupe, soit qu’ils sont incompatibles. On ne peut pas avoir choisi deux sommets dans le même groupe, puisqu’on en a choisi exactement un par groupe. Et on ne peut pas avoir choisi deux sommets incompatibles, parce qu’ils correspondraient à des littéraux x_i et \bar x_i, qu’on n’a choisi que des littéraux qui ont la valeur 1, et qu’on ne peut pas avoir en même temps x_i = 1 et \bar x_i = 1. Donc, toutes les paires dans les m sommets sont connectées entre elles, donc on a une clique de taille m, ce qu’on voulait démontrer.

Donc, on peut passer au deuxième point : si le graphe a une clique de taille m, la formule peut être satisfaite. Supposons, donc, que le graphe ait une clique de taille m. Comme les sommets d’un même groupe ne sont pas connectés entre eux, les sommets sont forcément dans des groupes différents. Si on a une clique de taille m, ça veut dire qu’on a un sommet dans chaque groupe de sommets. On peut donner à tous ces sommets la valeur 1. On ne peut pas avoir de clique qui contienne des sommets x_i et \bar x_i, puisqu’il n’y a pas d’arc entre deux sommets de ce type et que, par définition d’une clique, il faut que tous les arcs soient présents. Donc, si une clique de taille m existe, ça veut dire qu’on a trouvé un littéral par clause qui peut valoir 1, et que tous ces littéraux sont compatibles entre eux. Et donc qu’on peut satisfaire la formule correspondant au graphe, ce qu’on voulait démontrer aussi.

Donc, si on peut résoudre CLIQUE en temps polynomial, alors on peut résoudre SAT en temps polynomial ; SAT étant NP-difficile, CLIQUE l’est aussi, et donc CLIQUE est NP-complet, ce qui termine la preuve.

Le caractère NP-complet d’un problème est, quelque part, une « preuve » de la difficulté du problème en question, mais il faut atténuer ça largement. Déjà, ça ne présume en rien de la difficulté d’une instance donnée du problème. Ça ne présume en rien de la difficulté sur une certaine classe d’instances non plus. J’explique. Dire que CLIQUE est difficile, ça ne veut pas dire que, par exemple, décider si un triangle (qui est une clique de taille 3) est dans un graphe, même un gros graphe, est difficile. Parce que je peux prendre tous les ensembles de trois sommets, regarder s’ils forment un triangle, et conclure. Les ensembles de trois sommets, il y en a à peu près n³ dans un graphe à n sommets (plus exactement, il y en a n(n-1)(n-2)/6, mais, bon, à peu près n³), du coup je peux décider ça en temps polynomial (je fais n³ opérations qui vont pas prendre des plombes, c’est-à-dire vérifier si trois arcs donnés sont effectivement dans le graphe). Du coup, je peux décider 3-CLIQUE en temps polynomial. Bon, c’est pas pour ça que je vais être millionnaire, hein. Parce que le problème CLIQUE, il se limite pas à 3. Cela dit, si je veux, je peux aussi décider 1000-CLIQUE (clique de taille 1000) en temps polynomial. Bon, c’est un polynôme de degré 1000, mais on s’en fout 🙂

Par contre, dans le cas général, je ne peux pas décider si un graphe sur n sommets contient une clique de n/2 sommets, ou n/10000 sommets, ou même log n sommets en temps polynomial avec cet algorithme qui regarde tous les groupes de taille k (donc ici k = n/2, n/10000 ou log n) et qui regarde les arcs dans le groupe, parce que ça impliquerait de faire respectivement à peu près n^{n/2}, n^{n/10000} et n^{\log n} opérations, et que dans tous les cas c’est pas polynomial. Et, de manière générale, personne ne sait si c’est possible de faire ça en temps polynomial, puisque CLIQUE est NP-complet et qu’on ne sait pas si P est égal à NP. Beaucoup de gens supposent que non, mais personne ne sait.

Même là, ça ne présume en rien de la difficulté d’une instance donnée d’un problème. Supposons qu’on me file un graphe qui se trouve contenir n(n-1)/2 arcs pour n sommets. Alors je peux décider, sans trop de problème, que oui, ce graphe contient une clique de taille n/2, n/10000 et log n. Parce qu’un graphe de n(n-1)/2 arcs pour n sommets, ben il contient tous les arcs possibles pour le graphe : c’est un graphe complet (une clique sur n sommets), et comme une clique sur k sommets est un sous-graphe d’une clique sur n sommets… ben c’est pas bien difficile de répondre à la question. Idem si on me file un graphe avec 0 arcs et n sommets, je vais pas avoir beaucoup de mal à répondre que non, il ne contient pas de clique de taille n/2.

Dans le cas de SAT, on n’a aucun problème à résoudre les instances de 2-SAT (où toutes les clauses contiennent deux littéraux) en temps polynomial (et même linéaire). Il y a aussi des instances de SAT qui sont « faciles », par exemple celles où il y a peu de dépendances entre les clauses : on sait qu’on peut les résoudre, et on sait même comment (et, pour les gens intéressés, par « peu de dépendances », j’entends « qui tombent dans le cas du Lovász local lemma, dont l’application à SAT n’est pas évidente d’après la définition de la Wikipedia, mais qui devrait être plus claire ici).

De manière générale, il peut même être non trivial de créer des instances de problèmes NP-complets qu’on ne sait pas résoudre en temps polynomial. Notons au passage que c’est pas facile de prouver qu’on ne sait pas résoudre une instance donnée en temps polynomial. On peut exhiber des instances de problèmes qui sont difficiles (i.e. exponentielles) pour un algorithme donné, et triviales pour d’autres algorithmes…

Et c’est un peu ce qui se passe en pratique : on a des instances de problèmes pour lesquels on sait que le cas général est NP-complet (ou pire), et qu’on résout pourtant tous les jours en pratique. Une des raisons peut être que le problème est « petit » (c’est pas un drame de coller un algorithme exponentiel sur un problème de taille 4, quoi), mais ça peut aussi être parce que le problème fait partie d’une sous-classe d’instances sur laquelle le problème est facile. Donc, conclure qu’une instance de problème est difficile parce que le problème général l’est et abandonner (parce qu’on saura pas faire), c’est pas forcément une bonne idée, parce qu’il se peut qu’on n’ait pas considéré qu’on se trouve dans une restriction facile du problème !

Bref, comme d’habitude, « c’est pas aussi simple que ça ». En ce moment, je fais de la théorie, et du coup je m’intéresse plutôt aux problèmes eux-mêmes plutôt qu’à des instances données. Mais c’est parfois salutaire de se souvenir que des trucs « difficiles en théorie » peuvent s’avérer « faciles en pratique », ça change des trucs faciles en théorie qu’on sait pas faire en pratique… 🙂