Catégorie : Théorèmes à Périodicité Aléatoire

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).

TPA : Mincut, maxflow et réseaux de distribution d’eau

Publié le par Balise2 commentaires

Je viens de regarder une vidéo intitulée Efficient Maximum Flow Algorithms (en anglais), et comme je me demandais depuis quelques jours ce dont je pourrais bien parler dans un TPA, c’est arrivé à point nommé. Donc, aujourd’hui, on va parler de « max flow » ou, en français, « flot maximum ». Commençons par donner un petit exemple. Supposons qu’on veuille trimbaler de l’eau depuis un point A à un point B. Pour cela, on dispose d’un réseau de tuyaux qui ont tous une certaine capacité, en terme de nombre de litres par seconde qui peuvent y circuler, et on se pose la question de savoir combien de litres par seconde peuvent arriver au point A. Faisons un petit dessin :

On a le point A, le point B, quelques points intermédiaires reliés par des tuyaux, et la capacité de chaque tuyau est indiquée sur chaque tuyau. Sur un « petit » réseau comme celui-ci, on peut s’en sortir en regardant très fort le schéma et en tentant de répartir l’eau au maximum dans les tuyaux de façon à ce qu’aucun tuyau ne soit en surcapacité, sinon ça explose et ça fait désordre (spoiler : sauf erreur grossière de ma part, on arrive avec ce réseau à 5600 litres par seconde).

Évidemment, plus le réseau est compliqué, plus le calcul l’est, et au-delà d’une certaine taille ça devient franchement pénible à faire à la main. Beaucoup de gens se sont intéressés au problème, qui est à la fois considéré comme un problème « classique » voire « résolu » (par exemple la bibliothèque C++ Boost a quelques implémentations pour le résoudre), et comme un domaine actif de recherche (il est, par exemple, en couverture du numéro d’août des Communications of the ACM). Au lieu de parler de litres d’eau et de tuyaux, on utilise notre modèle préféré, qui est celui d’un graphe (comme le laisse vaguement sous-entendre mon petit schéma au-dessus) ; le type de graphe qu’on considère a cependant quelques éléments supplémentaires par rapport aux graphes que nous avons manipulés jusqu’ici, par exemple lorsque nous avons parlé du théorème des cinq couleurs. On a, comme d’habitude, des sommets (les points A, B et les points intermédiaires) et des arcs (les tuyaux). Dans les sommets, on a deux sommets « spéciaux », les points A et B, que l’on appelle la source et le puits. Sur les arcs, on a deux informations supplémentaires : la direction, représentée sur le schéma par une flèche (on dit que le graphe est dirigé) et la capacité. Et on veut trimbaler une certaine quantité de trucs, c’est-à-dire un « flot », de A à B. Le problème peut donc être formulé comme « étant donné un graphe dirigé, dont les arcs ont des capacités, et étant donnés une source et un puits, quelle est la quantité maximum de flot qui peut être transportée de A à B ? ». Les algorithmes permettant de répondre à cette question ne sont pas forcément très compliqués, mais ils sont plus longs que ce que j’ai envie de détailler ici. Il en existe plusieurs, et il peut être intéressant de ne pas utiliser les mêmes en fonction du graphe considéré (on n’utilisera par exemple pas forcément le même algorithme pour un graphe ayant peu ou beaucoup d’arcs).

Considérons maintenant un autre problème. Supposons que j’aie une fuite massive d’eau en B, et que je veuille couper l’eau qui arrive en B en coupant la circulation dans des tuyaux, et ce de la manière la plus « efficace » possible. L’efficacité, dans mon exemple imaginaire, se mesure en débit total des tuyaux que je coupe : je veux le minimiser, pour que la reprise du service soit la plus facile possible. Quels tuyaux dois-je couper ? Il faut impérativement que je coupe le tuyau direct à 4000 entre A et B (sinon j’ai forcément de l’eau qui continue à arriver en B). Je peux couper tout ce qui arrive en B : j’ai deux tuyaux à 1000 et un à 900, ça fait un « coût » total de 2900. Mais en regardant d’un peu plus près mon graphe, plutôt que de couper l’arrivée en B, si je coupe les départs en A (hors la ligne à 4000, qui est coupée quoi qu’il arrive), je peux m’en sortir pour 2300, c’est mieux. Et en regardant d’encore plus près, si au lieu de couper le tuyau à 2000 je coupe celui à 500 et celui à 800, je descends à 1600 (300 + 500 + 800). Coïncidence amusante, si je fais la somme de tous les tuyaux que je coupe (4000+300+500+800), j’obtiens le même nombre que le nombre maximum de litres que je peux faire circuler dans mon réseau entre A et B, c’est à dire 5600.

Il se trouve que ce n’est pas une coïncidence. Ce second problème est connu sous le nom de « min cut » ou, en français, « coupe minimum » : étant donné un graphe avec des coûts ou poids sur les arcs, comment déconnecter deux points donnés A et B en supprimant des arcs de manière à ce que la somme de leurs poids soit minimum ? Et étant donné un graphe dirigé avec des capacités/poids, le théorème dit « min cut/max flow » dit que, pour toutes les paires de sommets A et B du graphe, la quantité maximum de flot qui peut aller de A à B est égale au poids minimum des arcs à supprimer pour déconnecter A et B. Pour donner une idée de la preuve, on peut voir qu’une coupe (un ensemble d’arcs qui, lorsqu’on les supprime, déconnecte A et B) est un goulot d’étranglement : il est impossible de faire passer plus de flot entre A et B que la capacité des arcs qui forment cette coupe. Ça permet de déduire que le flot maximum est forcément inférieur (ou égal) au poids de la coupe minimum. L’autre direction (montrer que la valeur de la coupe minimum est effectivement atteinte) est un peu plus délicate. L’idée est que si on a un flot maximum, alors on a des arcs qui sont saturés, c’est-à-dire que pour que le flot puisse passer de A à B, il faut faire passer une valeur de flot égale à la capacité de l’arc par l’arc en question. Si ce n’était pas le cas, on pourrait augmenter le flot, ce qui ne peut pas arriver (puisqu’on considère un flot maximum). On peut aussi voir que tous les chemins de A à B contiennent au moins un arc saturé – sinon, on pourrait augmenter le flot sur le chemin en question. Maintenant, on explore le graphe en partant de A, en avançant sur tous les chemins possibles, et on marque tous les sommets que l’on peut atteindre sans passer par un arc saturé. Si on retire tous les arcs qui partent de cet ensemble de sommets marqués vers l’ensemble des sommets non-marqués, on obtient une coupe (sinon il existerait un chemin de A à B contenant un arc non saturé). De plus, ces arcs sont saturés, et la somme de leur poids est exactement la valeur du flot maximum (puisqu’il s’agit de l’ensemble des arcs qui sortent de l’ensemble des sommets marqués). Donc la valeur de flot maximum est égale à la valeur d’une coupe, elle-même supérieure ou égale à la valeur de la coupe minimum. Tout ceci nous permet de déduire que la valeur de la coupe minimum est égale à la valeur du flot maximum (puisqu’elle lui est à la fois inférieure ou égale et supérieure ou égale), et donc on est contents. Pour une certaine définition de « contents » – l’idée de la preuve que j’ai donnée ici n’est pas des plus rigoureuse (en espérant qu’elle soit correcte, il a fallu que je m’y reprenne à trois ou quatre fois…), mais j’espère en avoir donné tout de même une idée raisonnable !

Les algorithmes PPZ et PPSZ

Publié le par Balise2 commentaires

Aujourd’hui, on va causer 3-SAT, et on va en particulier causer de deux algorithmes très voisins, les  algorithmes PPZ et son petit frère PPSZ.

Il est plus que temps que je m’attaque à ce billet que j’aurais dû écrire depuis longtemps déjà. C’est un billet qui me tient à cœur parce que ça fait un an et demi que je fais des trucs autour de ces algorithmes, et que je commence à en avoir une assez bonne idée 🙂

Rappelons un peu de formalisme, histoire qu’on sache tous de quoi on est en train de parler. Pour une intro avec un peu plus de détails, voir mon billet sur SAT. J’ai n variables x_1,..., x_n, et j’ai des formules qui sont de ce type:

(x_1 \vee \bar x_2 \vee x_3) \wedge (x_1 \vee \bar x_3 \vee x_4) \wedge (x_6 \vee x_7 \vee x_8) \wedge ...

et je veux déterminer si, étant donné une telle formule, il existe des valeurs pour les variables x_1 à x_n (on parle d’une affectation) qui permettent d’évaluer la formule à 1 (on dit alors que la formule est satisfaite). Dans le cas général, c’est un problème NP-complet ; on a donc peu de chance de trouver un algorithme efficace qui marche à tous les coups. C’est bien le « à tous les coups » qui m’intéresse ici : je me demande ce que je peux garantir pour mon algorithme, même si je tombe sur la formule la plus difficile du monde. Le « record » actuel pour ce type de garantie est actuellement pour l’algorithme PPSZ, qui est un algorithme aléatoire, et qui est le sujet de ce billet. Comme je parle d’algorithme aléatoire, il me paraît un poil plus intuitif de parler de probabilité de succès que de temps d’exécution même si, on l’a vu, les deux notions sont liées – puisqu’il suffit de répéter un algorithme aléatoire avec une probabilité de succès donnée suffisamment de fois pour être raisonnablement sûr qu’il réussisse. Ça fait un peu Shadok, mais passons. Je vais aussi, dans ce qui suit, supposer que j’ai une formule pour laquelle je sais qu’il existe un ensemble de valeurs qui la satisfont, et que je veux « juste » trouver les valeurs en question. En pratique, les deux problèmes sont liés aussi : je peux supposer que si mon algorithme trouve ces valeurs, ben c’est qu’elles existent, et que si je cherche suffisamment longtemps sans les trouver, ça serait quand même pas de bol qu’elles existent et que je les aie ratées.

L’algorithme aléatoire le plus simple auquel on peut penser est de prendre des valeurs au hasard, de vérifier si elles satisfont la formule, et de recommencer si c’est pas le cas. Toutes les affectations possibles ont la même probabilité (si je les choisis au hasard comme ça) – et j’en ai 2^n – parce que pour chaque variable, j’ai deux possibilités, 0 ou 1. Donc la probabilité de succès de cet algorithme, si j’ai \ell affectations qui satisfont ma formule, est de \ell / 2^n : parmi les 2^n choix que je peux faire, j’en ai \ell qui marchent.

Après, il y a moyen de faire les choses de manière un peu plus intelligente. Plutôt que d’affecter les variables toutes en même temps, je vais les affecter une à une. Qu’est-ce que ça change ? Ça change que si j’ai un truc qui est trivialement idiot à faire, je peux éviter de le faire. Ce qui veut dire qu’il faut que j’explique ce que ça veut dire « trivialement idiot ». Supposons que j’aie une formule très simple qui soit juste (x_1 \vee x_2 \vee x_3). Si j’ai choisi pour x_1 la valeur 0 et pour x_2 la valeur 0, il est « trivialement idiot » de choisir 0 pour x_3 puisque je n’ai alors aucune chance de satisfaire la formule. Donc par « trivialement idiot », je veux dire qu’il y a une clause qu’il n’y a plus qu’une seule chance de satisfaire, c’est-à-dire qu’on a déjà affecté des valeurs à deux variables sur les trois de la clause, et que la clause n’est toujours pas satisfaite. Si j’utilise mon algorithme précédent, j’ai une probabilité 7/8 de trouver une affectation satisfaisante (parce qu’avec probabilité 1/8 je tombe sur 000 pour mes variables et ma formule n’est pas satisfaite). Si j’essaie d’éviter les trucs trivialement idiots… ben déroulons le truc. Je commence par x_1, il n’y a pas de truc trivialement idiot à éviter, donc je prends une valeur au hasard. Je continue par x_2 ; là encore, il n’y a pas de truc trivialement idiot à éviter, donc je prends une valeur au hasard. J’arrive à x_3, et là j’ai deux possibilités. Si x_1 et x_2 ont été mis tous les deux à 0, j’ai un truc trivialement idiot à éviter, c’est de mettre x_3 à 0, donc j’évite ça, je mets x_3 à 1, et ma formule est satisfaite. Si x_1 ou x_2 a été mis à 1, quoi que je fasse sur x_3 sera valide, donc je ne peux pas me tromper. Sur ce cas spécifique, rien qu’en évitant les trucs trivialement idiots, mon algorithme passe à une probabilité de succès de 1.

C’est pas toujours aussi idyllique, évidemment – là les choses se passent bien parce que j’ai une seule clause, beaucoup d’affectations valides, et qu’on est contents. Maintenant, un cas un peu plus sioux : considérons la formule

(x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_2 \vee \bar x_3) \wedge (x_1 \vee \bar x_2 \vee x_3) \wedge (x_1 \vee \bar x_2 \vee \bar x_3) \wedge (\bar x_1 \vee x_2 \vee x_3) \wedge (\bar x_1 \vee x_2 \vee \bar x_3)

Deux affectations satisfont cette formule : x_1 = 1, x_2 = 1, x_3 = 0  et x_1 = 1, x_2 = 1, x_3 = 1. Avec mon algorithme « simple », la probabilité de succès est de 2/8 = 1/4. Avec mon algorithme qui cherche à éviter les trucs « trivialement idiots »… aussi, dans certaines conditions. Si je commence par la variable x_1 et que je la mets à 0, je n’ai aucune chance d’obtenir une affectation satisfaisant la formule. Si je continue par la variable x_2 et que je la mets à 0, idem. Donc il faut que je mette x_1 et x_2 à 1 tous les deux, ce qui arrive avec une probabilité 1/4 ; x_3 peut être mis à n’importe quelle valeur, donc si on n’a pas fait d’erreur jusqu’ici on n’en fera pas non plus à la dernière étape. Dans ce cas, donc, la probabilité de succès avec ou sans la détection de trucs « trivialement idiots » est la même. Sauf que… si on traite les variables non pas dans cet ordre là mais, par exemple, dans l’ordre x_3 x_2 x_1… Pour la première variable, x_3, on ne peut pas faire d’erreur, quelle que soit la valeur d’affectation. Pour x_2, on ne peut pas détecter de truc trivialement idiot, donc on la met à la bonne valeur avec une probabilité 1/2. Mais si cela arrive, la clause (x_1 \vee \bar x_2 \vee \bar x_3) ou la clause (x_1 \vee \bar x_2 \vee x_3) (selon la valeur affectée à x_3) indiquera à l’algorithme que mettre x_1 à 0 est trivialement idiot, ce qu’il faut éviter. Avec cet ordre de variables, la probabilité de succès de notre algorithme amélioré passe à 1/2. Il y a donc de « bons » ordres de variables et de « mauvais » ordres de variables (on parle de permutations). Comme il est difficile de savoir avant de commencer si une permutation est bonne ou mauvaise (ou comment trouver une bonne permutation), on fait comme d’habitude : on prend une permutation au hasard et on espère qu’en moyenne ça marche bien.

C’est exactement ce que fait l’algorithme PPZ (nommé d’après ses trois auteurs, Ramamohan Paturi, Pavel Pudlák et Francis Zane, dans un papier intitulé Satisfiability Coding Lemma) :

  • On part d’une formule F sur n variables, et on commence avec une affectation vide (on n’affecte aucune valeur aux variables pour l’instant).
  • On choisit un ordre aléatoire pour les variables, et on les traite une par une dans cet ordre :
    • Pour la variable courante x_i, si x_i = 0 est trivialement idiot, on affecte 1 à x_i
    • Sinon, si x_i = 1 est trivialement idiot, on affecte 0 à x_i
    • Sinon, on affecte une valeur aléatoire à x_i
    • Et on passe à la variable suivante.
  • Si l’affectation qu’on trouve satisfait la formule, c’est terminé ! Sinon, on recommence au départ.

L’analyse de la probabilité de succès de l’algorithme est relativement simple. Sans rentrer dans les détails, l’idée c’est que si je n’ai pas le choix pour une variable (c’est-à-dire si la mettre à 0 ou à 1 fait que l’affectation ne peut pas être satisfaisante), alors j’ai au moins une clause qui rend ce choix trivialement idiot dans au moins une permutation sur trois (parce que dans un cas sur trois, la variable en question arrivera en dernier dans la clause en question). J’ai toujours des choix aléatoires pour certaines variables, donc l’algorithme peut toujours se vautrer lamentablement, mais la probabilité de ne pas se vautrer est meilleure que si on prend juste une affectation au hasard.

Après, le lecteur attentif se sera peut-être dit « ouiiii mais si j’assigne x_1 à 1, j’ai à la fois une clause (\bar x_1, x_2, x_3) et une clause (\bar x_1, x_2, \bar x_3), donc quelque part c’est AUSSI trivialement idiot de mettre x_2 à 0… ». Le lecteur attentif est un petit malin. Et c’est aussi, quelque part, ce que fait l’algorithme PPSZ (nommé d’après les trois auteurs précédents + Michael Saks, dans un papier intitulé An Improved Exponential-Time Algorithm for k-SAT) : plutôt que de regarder les clauses une à une pour voir si par hasard on peut éliminer un choix trivialement idiot, on en regarde beaucoup à la fois (typiquement \log \log n, où n est le nombre de variables de la formule) pour tenter d’en tirer les mêmes conclusions. il y a un nombre sous-exponentiel d’ensembles de \log \log n clauses, et examiner chacun d’entre eux peut se faire en temps sous-exponentiel aussi (on peut se contenter de regarder toutes les valeurs possible pour le sous-ensemble de variables qui interviennent dans ce sous-ensemble de clauses). Les mauvais choix ne peuvent plus nécessairement être qualifiés de « trivialement idiots » mais peut-être de « manifestement idiots » ; le résultat est le même : si on peut les détecter, autant les éviter. Pour le coup, l’analyse de la probabilité de succès de cet algorithme est (beaucoup) plus complexe ; pour la petite histoire, lorsque l’article original a été publié, les auteurs n’avaient établi la probabilité de succès que dans le cas où la formule n’avait qu’une seule affectation satisfaisante (l’analyse du cas général n’arrivait à prouver qu’une probabilité de succès plus basse). La preuve plus générale a été établie par Timon Hertli (3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General), mais il s’est passé plus de dix ans entre l’introduction de l’algorithme et la preuve en question. Une version « lisible » (pour une certaine définition de « lisible, admettons-le) de la preuve en question est disponible dans ma thèse de semestre (chapitre 2) – elle est difficile à résumer en moins de, mettons, 8 pages (heu, déjà 8 pages, c’est challenge, en fait.)

J’ai travaillé autour de ces algorithmes depuis un an et demi (pas complètement par hasard, Timon dont je parle précédemment étant doctorant à l’ETH… et mon superviseur sur tout ce que j’ai fait), et pour le coup c’est probablement LE sujet sur lequel je me sens prête à répondre à BEAUCOUP de questions 🙂

 

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.