Probabilités – Partie 2

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

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

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… 🙂

Le problème SAT

Je vais expliquer un peu ce qu’est le problème SAT, parce que j’aurai l’occasion d’en reparler plus en détail bientôt (pour une certaine définition de bientôt dépendant de ma charge scolaire 🙂 ). C’est aussi une des briques fondamentales liées à la question « P = NP » ; j’avais commencé à écrire ce billet dans un prochain billet à propos de problèmes NP-complets, mais je crois que je peux faire un billet complet sur le sujet, ça m’évitera d’avoir la tentation de « faire vite ». L’autre raison pour laquelle je veux pas faire vite, c’est que je fais en ce moment un « projet de semestre » sur un sujet très très très voisin, et comme j’ai aussi l’intention de faire un billet sur ce que je fais plus précisément, ben ça ça sera fait.

SAT est une abréviation pour « boolean satisfiability problem », ou en français « problème de satisfaisabilité booléenne ». L’idée, c’est qu’on a une formule booléenne, ou formule SAT, et qu’on cherche à décider si on peut la résoudre ou pas.

Une formule SAT peut, par exemple, avoir cette tête là :

(x \vee y \vee z) \wedge (\bar x \vee \bar y) \wedge (\bar x \vee y \vee z)

Il y a plusieurs éléments dans ce machin. Le premier élément, ce sont les variables – ici, x, y, z. On peut les voir comme les « inconnues » d’une équation : on veut ici savoir si on peut trouver des valeurs pour x, y et z. En plus de ça, on est dans un univers un peu bizarre, l’univers booléen : x, y et z ne peuvent prendre que la valeur 0 ou la valeur 1.

Après, il y a des symboles bizarres. \vee, ça veut dire « ou », et \wedge, ça veut dire « et ». Les petites barres au-dessus de certaines lettres indiquent un négation. Les symboles se lisent comme ça :

\begin{array}{|c|c||c|c|c|c|} \hline x & y & \bar x &\bar y & x \vee y & x \wedge y \\ \hline 0 & 0 & 1 & 1 & 0 & 0 \\ \hline 0 & 1 & 1 & 0 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 \\ \hline 1 & 1 & 0 & 0 & 1 & 1 \\ \hline \end{array}

Ou, si j’écris ça en toutes lettres :

  • si x = 1, alors \bar x = 0, sinon \bar x = 1 (\bar x prend la valeur inverse de x)
  • si x = 1, alors x \vee y = 1 ; si y = 1 alors x \vee y = 1 ; si x = 0 et y = 0, alors x \vee y = 0 (« x OU y vaut 1 »). Il faut préciser que quand on dit « ou » dans ce contexte, ce n’est pas dans le même sens que « fromage ou dessert » : si on prend du fromage et du dessert, alors on prend du fromage ou du dessert (puisqu’on prend au moins l’un des deux). 
  • si x = 1 et y = 1, alors x \wedge y = 1, sinon x \wedge y = 0 (« x ET y valent tous les deux 1 »).

On peut combiner tous ces machins de la manière qu’on veut pour obtenir des formules booléennes. On s’intéresse en particulier aux formules du type que j’ai donné précédemment, qui sont appelées des formules « CNF » (pour « conjunctive normal form »). Ce type de formule est défini comme un ensemble de clauses, toutes reliées entre elles par des symboles \wedge (« et »). Une clause se compose d’un ou plusieurs littéraux (un littéral, des littéraux), qui sont soit une variable (par exemple x), soit sa négation (par exemple bar x) tous reliés entre eux par des symboles \vee (« ou »). On veut donc que toutes les clauses aient comme valeur 1 (parce qu’on veut que la première ET la deuxième ET la troisième ET toutes les suivantes aient la valeur 1). Et le fait que chaque clause ait la valeur 1, ça se traduit par le fait qu’au moins un des littéraux de la formule ait la valeur 1 (parce qu’on veut que le premier littéral OU le deuxième OU le troisième OU… ait la valeur 1). Même remarque que précédemment, il peut arriver que tous les littéraux aient la valeur 1, ça renvoie quand même toujours 1. 

La question posée par une instance de SAT, c’est « est-ce que je peux trouver des valeurs pour toutes les variables de manière à ce que la formule complète ait pour valeur 1 ? ».

Reprenons l’exemple précédent, et nommons la formule F:

F = (x \vee y \vee z) \wedge (\bar x \vee \bar y) \wedge (\bar x \vee y \vee z)

Si je veux regarder s’il existe des valeurs pour x, y et z qui font que la formule F vaut 1 (c’est-à-dire pour que la formule soit satisfaite), je peux toutes les énumérer et regarder ce qu’il se passe.

\begin{array}{|c|c|c||c|c|c||c|} \hline x & y & z & x \vee y \vee z & \bar x \vee \bar y & \bar x \vee y \vee z & F \\  \hline 0 & 0 & 0 & 0 & 1 & 1 & 0 \\  \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 \\  \hline 0 & 1 & 0 & 1 & 1 & 1 & 1\\  \hline 0 & 1 & 1 & 1 & 1 & 1 & 1\\  \hline 1 & 0 & 0 & 1 & 1 & 0 & 0 \\  \hline 1 & 0 & 1 & 1 & 1 & 1 & 1 \\  \hline 1 & 1 & 0 & 1 & 0 & 1 & 0\\  \hline 1 & 1 & 1 & 1 & 0 & 1 & 0\\  \hline \end{array}

Mon petit tableau répond à la question « est-ce qu’il existe des valeurs pour x, y et z de sorte à ce que la formule F vaille 1 » (la réponse est oui), et il va même plus loin en donnant lesdites valeurs (par exemple, x = 1, y = 0, z = 1 sont des valeurs valides pour satisfaire la formule).

Le problème, c’est que c’est pas vraiment gérable dès qu’on commence à avoir beaucoup de variables. La raison, c’est que pour chaque variable, il faut que je regarde ce qu’il se passe pour sa valeur 0 et pour sa valeur 1. Donc j’ai deux choix pour la première variable ; deux choix pour la deuxième variable ; deux choix pour la troisième variable, etc. Les choix en question se multiplient : on voit ça dans le tableau au-dessus, il faut que je fasse une ligne pour toutes les combinaisons possibles de valeurs de variables. Donc, pour 3 variables, 2*2*2 = 2³ = 8 lignes. Pour 5 variables, on est déjà à 2*2*2*2*2 = 2⁵ = 32 lignes, et ça commence à être relou à faire à la main. Pour 20 variables, on est à 2²⁰ = 1.048.576 lignes, et ça commence à ne pas être vraiment instantané à calculer. Et ça augmente de plus en plus vite : les joies de la fonction puissance.

Pour ceux qui ont suivi les explications précédentes, ce n’est PAS un algorithme en temps polynomial ; c’est un algorithme en temps exponentiel. D’autant plus que je ne considère là que l’énumération de tous les cas et que je ne regarde même pas combien de temps il me faut pour conclure dans chacun des cas.

Du point de vue « classe de complexité », SAT fait partie des problèmes de la classe NP. Si on me donne une formule et des valeurs pour toutes les variables de la formule, je peux vérifier efficacement que, effectivement, ça marche : je peux vérifier qu’une formule peut être satisfaite si on m’en fournit la preuve.

Par contre, on ne sait pas s’il fait partie des problèmes de la classe P : on ne sait pas s’il existe un algorithme polynomial permettant de décider si, oui ou non, une formule peut être satisfaite ou non. On ne sait pas non plus s’il est en dehors des problèmes de la classe P : on ne sait pas s’il faut nécessairement un algorithme « plus puissant » qu’un algorithme polynomial pour le résoudre. Et répondre à cette question (et le prouver correctement) permettrait de répondre à la question « est-ce que P = NP ? » – mais pour ça, il faut que je parle de problèmes NP-complets, et je ferai ça dans le prochain billet 🙂

EDIT : bon, je re-précise un ou deux trucs, parce que tripa a pas COMPLÈTEMENT tort dans les commentaires. Quand je dis « on ne sait pas si », je veux parler du cas général, c’est-à-dire de n’importe quelle formule SAT. Après, il y a des cas où c’est « facile », c’est-à-dire qu’on peut conclure très vite. C’est par exemple le cas si on se restreint à des clauses avec deux littéraux (2-SAT) : dans ce cas précis, il y a un algorithme qui permet de conclure en temps linéaire (c’est-à-dire, en gros, qu’on lit la formule, et qu’on sait.) La difficulté intrinsèque du problème général ne donne pas vraiment d’indication sur les instances individuelles. C’est plutôt un point que je traiterai dans le billet suivant, parce que c’est aussi important de s’en souvenir, mais, bon. Tout ça pour dire que SAT c’est dur, mais qu’il y a des instances du problème qui sont faciles, et qu’il faut éventuellement se poser les bonnes questions avant de conclure qu’on n’a aucune chance de résoudre une formule donnée 🙂

Le problème « P est-il égal à NP ? »

Bon, je crois que j’ai tout ce qu’il me faut maintenant que j’ai parlé un petit peu de complexité (partie 1 et partie 2) pour attaquer un morceau sympa, qui est d’expliquer ce qu’il y a derrière la question « P est-il égal à NP ? », que je vais abréger par « P = NP » (de façon assez ironique, on verra pourquoi plus tard). C’est vendredi, vous aurez le week-end pour lire (et peut-être un peu plus parce que je retourne en cours lundi 😉 ).

Le problème P = NP est un des problèmes ouverts (c’est-à-dire non résolu) les plus célèbres, sinon le plus célèbre. Il fait d’ailleurs partie des problèmes du prix du millénaire, une série de 7 problèmes énoncés en 2000 et dont la résolution correcte permettrait à son auteur de toucher un million de dollars. Un seul de ces 7 problèmes a été résolu, la conjecture de Poincaré ; Grigori Perelman l’a démontrée, ce qui lui a valu la médaille Fields (c’est l’équivalent du Nobel pour les maths) et, donc, le million de dollars en question ; il a refusé les deux.

Bon, assez de contexte, maintenant parlons de la bête. P et NP sont ce qu’on appelle des « classes de complexité ». Les classes de complexité sont des ensembles de problèmes qui ont des propriétés communes. L’idée, c’est de prendre des problèmes (par exemple : « est-ce que je peux aller d’un point A à un point B sur mon graphe en moins de 15 étapes ? ») et de les ranger dans des petites cases en fonction de leurs propriétés, en particulier de leur complexité en temps (le temps qu’il faut pour les résoudre) et en espace (la quantité de mémoire qu’il faut pour les résoudre). On s’intéresse ici à la complexité « dans le pire des cas ».

J’ai expliqué dans les billets sur la complexité algorithmique ce que ça voulait dire pour un algorithme de s’exécuter dans un temps donné. Dire qu’un problème se résout en un temps donné, c’est dire qu’on sait le résoudre dans ce temps, c’est-à-dire qu’on a un algorithme qui s’exécute dans ce temps et qui renvoie la bonne solution. Pour reprendre les exemples précédents, on a vu qu’on pouvait trier un ensemble d’éléments (livres… ou autres) en temps n² et en temps n log n. Il se trouve que, dans les modèles de calcul classiques, on ne peut pas faire « mieux » que ce n log n (c’est prouvé). On dit que la complexité du tri est n log n, et on peut dire qu’on peut trier des éléments en temps polynomial.

Un algorithme en temps polynomial est un algorithme qui se termine en un nombre d’étapes inférieur à n^k, avec n représentant la taille de l’entrée, et k représentant un nombre quelconque (y compris de très grands nombres, tant qu’ils ne dépendent pas de n lui-même). Le nom vient du fait que les fonctions de type x \mapsto x, x \mapsto x^2, x \mapsto x^{10} + 15x^5 et x \mapsto x^k s’appellent des fonctions polynomiales. Comme je peux trier des éléments en temps n² (et même n log n, ce qui est « mieux »), le tri est résolu en temps polynomial. Ça marcherait aussi si je pouvais trier des éléments en temps n⁴⁷⁹, ça serait aussi polynomial. L’énorme avantage des polynômes, c’est que ça se combine vachement bien. Si je fais deux opérations polynomiales, je reste en temps polynomial. Si je fais un nombre polynomial d’opérations polynomiales, je reste en temps polynomial. Mon polynôme « grossit » (il passe par exemple de n² à n⁵), mais il reste un polynôme.

Bon, et là il va falloir que j’explique la différence entre problème et instance du problème, sinon je vais dire des bêtises (et j’aime pas dire des bêtises). En gros, un problème regroupe toutes les instances d’un problème. Si je dis « je veux trier ma bibliothèque », c’est une instance du problème « je veux trier une bibliothèque quelconque ». Si je m’intéresse au plus court chemin entre deux points sur un graphe donné (par exemple la carte du métro), c’est une instance du problème « plus court chemin dans un graphe », où on considère tous les graphes arbitraires de taille également arbitraire. Le problème est le « concept général », l’instance est « un exemple concret du problème général ».

La classe de complexité P regroupe tous les problèmes dits « de décision » qu’on peut résoudre en temps polynomial. Un problème de décision, c’est un problème qui appelle une réponse de type oui/non. Ça peut paraître une restriction énorme ; en pratique, pas tant que ça. Plutôt que de demander le « plus court chemin », on peut par exemple demander s’il existe « un chemin de distance inférieur à X », et faire varier X jusqu’à trouver le X « limite ». On peut faire ça avec un nombre de requêtes polynomial, donc, si on peut résoudre le problème de décision en temps polynomial, on peut aussi résoudre le problème « numérique » en temps polynomial (Je simplifie salement ici, je crois que ça ne serait pas vrai en général et qu’il me faut des conditions supplémentaires pour que ça marche.) Et une instance de ce problème décisionnel de taille de chemins, ça peut par exemple être « considérant la carte du métro parisien, existe-t-il un chemin allant le La Motte Piquet Grenelle à Belleville en moins de 20 stations, sans prendre en compte les correspondances » (la réponse est oui) ou « en moins de 10 stations » (j’ai pas vérifié complètement, mais je crois que la réponse est non).

Un autre « type » de problème de décision est celui qui regroupe les problèmes de colorabilité de graphes.  J’aime bien ce genre d’exemple parce que je peux faire des petits dessins et c’est, je crois, facile à expliquer 🙂 (Bon, c’est pas très daltonien-friendly par contre. Si ya des daltoniens, râlez, je referai les figures avec des numéros pour les couleurs, mais là j’ai la flemme.) On prend un graphe, c’est-à-dire un ensemble de sommets reliés par des arcs, et on veut colorier les sommets de façon à ce que deux sommets n’aient pas la même couleur s’ils sont reliés par un arc. Les questions de colorabilité sont des questions de type « est-ce que je peux colorer mon graphe avec 2, 3, 5, 12 couleurs ». Le problème « non-décisionnel » est celui qui demande quel est le nombre minimal de couleurs nécessaires pour colorer le graphe avec la contrainte exprimée ci-dessus.

Bon, quelques exemples – des instances du problème, donc 🙂

Un graphe « triangle » (trois sommets reliés par trois arcs) ne peut pas être coloré avec seulement deux couleurs, il m’en faut 3 :

3clique

Par contre, un graphe « carré » (trois sommets reliés en carré par quatre arcs) peut être coloré avec deux couleurs seulement :

carre

Je peux avoir des graphes avec un nombre de sommets (et d’arcs) très élevé qui peuvent être colorés avec deux couleurs seulement, pour autant qu’ils suivent ce genre de structure :

bipartite

Et je peux avoir des graphes qui demandent un grand nombre de couleurs – une par sommet ! – si tous les sommets sont reliés les uns aux autres, comme sur celui-ci :

8clique

Bon, et c’est là que ça devient intéressant (à mon avis). On sait répondre en temps polynomial à la question « est-ce que ce graphe est colorable avec deux couleurs ? » pour n’importe quel graphe (le « polynomial » ici est en fonction du nombre de sommets du graphe). Pour décider ça, on commence par colorer un sommet, n’importe lequel, du graphe, en bleu. On colorie tous ses voisins, c’est-à-dire tous les sommets qui lui sont reliés par un arc, en rouge (parce que vu que le premier est bleu, tous ses voisins doivent être rouges, sinon on contredit la contrainte qu’on a définie). On essaye de colorier tous les voisins des sommets rouges en bleu, et ainsi de suite. Si on arrive à tout colorier avec cet algorithme, le graphe peut être coloré avec deux couleurs (parce qu’on vient précisément de le faire !). Sinon, c’est qu’un sommet a une contrainte qui l’oblige à être rouge (un voisin bleu) et une contrainte qui l’oblige à être bleu (un voisin rouge). C’est pas complètement évident de voir que ça veut dire que le graphe ne peut pas être coloré avec deux couleurs, mais il se trouve que c’est le cas. L’algorithme se contente, en gros, de parcourir tous les sommets dans un certain ordre et de colorer au fur et à mesure ; on ne visite les sommets qu’une fois ; on vérifie au pire tous les autres sommets (s’ils sont tous connectés) avant de colorier ; si pour chaque sommet je fais au pire une comparaison pour tous les autres sommets et que j’ai n sommets, je pense qu’on peut se convaincre, sans rentrer dans les détails, qu’on fait au pire n*(n-1) opérations, et que l’algorithme est polynomial. (Je ne rentre pas dans les détails ici parce que ça dériverait vilement du sujet ; mais si vous voulez plus de détails, râlez en commentaire et j’essaierai de développer plus).

Par contre, pour la question « est-ce que le graphe est colorable avec trois couleurs ? », ben… on n’a pas encore trouvé d’algorithme en temps polynomial pour répondre à la question pour n’importe quelle instance du problème, c’est à dire pour n’importe quel graphe. Et, pour des raisons que je vais expliquer, genre, dans un prochain billet, si vous trouvez un algorithme (correct !) qui permette de répondre à la question en temps polynomial, il y a de bonnes chances que ça vous fasse gagner une certaine célébrité, possiblement une certaine haine de la part des gens qui font de la cryptographie, et un million de dollars. Intéressant, non ?

L’autre truc intéressant, c’est que si je vous donne un graphe déjà coloré, et que je vous dit « j’ai coloré ce graphe avec 3 couleurs », vous pouvez vérifier, en temps polynomial aussi, que je n’essaie pas de vous enfumer. Il suffit de regarder tous les arcs l’un après l’autre et de vérifier que les deux sommets de l’arc sont colorés avec des couleurs différentes. Facile. Et polynomial.

Ce genre de problème « facilement vérifiable » constitue la classe de complexité NP. Sans partir dans la définition formelle, voilà une idée du machin : un problème décisionnel fait partie de la classe NP si, pour toutes les instances auxquelles je peux répondre « oui », j’ai une « preuve » qui me permet de le vérifier en temps polynomial. Cette « preuve » me permet, en quelque sorte, de répondre à l’interjection « même pas cap ! », ce à quoi je réponds, dans le cas de la colorabilité, par « ben si, tu vois, si je colore comme ça, ça marche, ça prouve bien que je peux le faire avec trois couleurs ». Notez ici que je ne dis rien sur ce qu’il se passe quand je dois répondre « non » à l’instance. Une des raisons, c’est que c’est souvent « plus difficile » de prouver qu’un truc n’est pas faisable que de prouver qu’il l’est. Je peux prouver qu’un truc est faisable en le faisant ; si j’arrive pas à faire un truc, tout ce que ça prouve c’est que j’arrive pas à le faire.

Donc, pour récapituler :

  • P est la classe des problèmes auxquels j’arrive à répondre par « oui » ou par « non » en temps polynomial
  • 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.

La remarque suivante, c’est que les problèmes qui sont dans P sont aussi dans NP, parce que si j’arrive à répondre moi-même à la question « oui » ou « non » en temps polynomial, je peux être convaincue en temps polynomial que la réponse est « oui » si c’est effectivement le cas (il me suffit d’exécuter l’algorithme polynomial qui me répond « oui » ou « non », et de vérifier qu’il répond « oui »).

La question à, littéralement, un million de dollars, c’est de savoir si tous les problèmes qui sont dans NP sont aussi dans P. Informellement, est-ce que le fait de pouvoir « voir facilement » (c’est à dire en temps polynomial) si un problème a une réponse « oui », pour peu qu’on me fournisse une preuve, veut aussi dire qu’on peut le « résoudre facilement ». Si c’est le cas, alors tous les problèmes de P sont dans NP, tous les problèmes de NP sont dans P, et donc la classe P et la classe NP contiennent exactement les mêmes problèmes, c’est à dire P = NP. Si ce n’est pas le cas, alors il y a des problèmes de NP qui ne sont pas dans P, et donc P ≠ NP.

L’immense majorité des gens qui font des maths pensent que P ≠ NP, mais personne n’a encore réussi à le prouver. Et beaucoup de gens ont essayé 🙂

Ça serait très, très, très surprenant pour tout le monde qu’on arrive à prouver que P = NP. Ça aurait probablement de grosses conséquences, parce que ça indiquerait qu’on a une chance de résoudre des problèmes actuellement considérés comme « difficiles » dans des temps « acceptables ». Une bonne partie de la cryptographie actuelle se base sur le fait non pas qu’il est « impossible » de faire certaines opérations, mais que c’est « difficile » de les faire, c’est à dire qu’on ne connaît pas d’algorithme rapide pour les faire. Ça ne casserait probablement pas immédiatement tout (parce que ça serait probablement difficile à appliquer directement et que ça prendrait du temps), mais il faudrait sans doute se dépêcher de trouver autre chose avant que ça arrive.

Et le dernier truc rigolo, c’est que pour prouver que P = NP, il « suffit » de trouver un algorithme en temps polynomial pour un des problèmes dits « NP-complets » – ce dont je parlerai dans un prochain billet, parce que celui-ci commence à tirer en longueur. La colorabilité à trois couleurs fait partie de ces problèmes NP-complets.

Personnellement, je trouve ça absolument fascinant qu’un problème aussi « facile » à conceptualiser ait de telles implications quant à sa résolution. Et j’espère qu’après avoir lu ce que je viens d’écrire, vous pouvez au moins comprendre ma fascination, à défaut peut-être de la partager 😉

Compréhension mathématique

Allez, après les billets un peu velus qu’étaient Introduction à la complexité algorithmique, 1/2 et Introduction à la complexité algorithmique, 2/2, un billet un peu plus light et un peu plus « méta », probablement. Et qui part dans le n’importe quoi, probablement aussi. Il est probable également qu’à la fin de la lecture de cet article vous soyez convaincu que je suis, dans le meilleur des cas, très exigeante avec moi-même, et dans le pire des cas que vous soyez  tentés de me passer un chouette pyjama blanc qui s’attache dans le dos 🙂

Je suis assez fascinée par le fonctionnement du cerveau humain. Pas par la manière dont il fonctionne, ça j’en sais rien, mais par le fait même qu’il fonctionne. Le concept de lire, par exemple, ça continue à m’émerveiller. J’y reviendrai sans doute à l’occasion 🙂 (parce que ça touche probablement plus à l’apprentissage qu’à la compréhension, et que c’est deux sujets connexes, mais différents). (Enfin je crois.)

Bref, je passe pas mal de temps à réfléchir à la manière dont je réfléchis, et à la manière d’améliorer la manière dont je réfléchis, ou à tenter optimiser ce que je fais pour que ça corresponde à ma manière de réfléchir. Et dans cette réflexion, j’ai en particulier redéfini ce que j’entendais par « compréhension ».

Je me limite ici explicitement à un type de compréhension bien particulier, que j’appellerai « compréhension mathématique » à défaut d’un terme plus adéquat. Je sais même pas si je peux exactement définir le terme ; alors je vais essayer d’expliquer l’impression que ça fait. Ça peut paraître bizarre de relier la compréhension aux impressions, mais en ce qui me concerne j’ai, peut-être paradoxalement, appris à faire confiance à mon ressenti pour évaluer ma compréhension des choses.

Il m’arrive fréquemment de me lamenter que je ne comprends plus aussi vite qu’avant ; je me demande dans quelle mesure ça ne vient pas du fait que je suis plus exigeante envers moi-même. Il fut une époque où ma définition de « compréhension » était au niveau de « ce que tu racontes a l’air logique, et je vois l’enchaînement logique de ce que tu fais au tableau, et je vois en gros ce que tu fais ». J’ai aussi un souvenir assez cuisant d’incidents du genre :

« Tiens, tu devrais lire cet article.
— OK.
<quelques heures plus tard>
— J’ai finiiiii !
— Déjà ?
— Bin, ouais… je lis vite…
— Et t’as tout compris ?
— Bin… ouais…
— Y compris pourquoi <point obscur mais potentiellement crucial du papier> ?
<gros blanc, soupir et explications> » (pas de mon fait, les explications.)

Évidemment, c’était complètement de la bonne foi de mon côté. J’étais persuadée d’avoir effectivement compris, avant qu’on ne me démontre que j’avais raté pas mal de choses.

Depuis, j’ai appris plusieurs choses. La première est que « comprendre vaguement » n’est pas « comprendre », du moins pas à mon propre niveau (actuel) d’exigence. C’en est la première étape. Ça peut aussi en être la dernière étape, si c’est un sujet sur lequel je peux/veux me contenter de connaissances « de surface ». J’ai probablement gagné pas mal en modestie et je dis probablement beaucoup plus souvent que je n’ai qu’une vague idée de certains sujets.

La deuxième chose, c’est que oui, comprendre, ça prend du temps. Aujourd’hui, j’estime que je commence à avoir une compréhension « correcte » (encore une fois, à mon niveau d’exigence, qui est probablement élevé) à la troisième ou quatrième lecture d’un article de recherche. En-dessous de ça, j’ai « une vague idée de ce que raconte le papier ».

La troisième chose, et ça pourtant c’est une citation qui revenait souvent à la maison, c’est que « la répétition est l’âme de l’enseignement bien compris ». Ça aide beaucoup d’avoir au moins une exposition aux notions avant de commencer quelque chose de nouveau et velu. La première exposition est une grande baffe dans la gueule, la deuxième commence à aller mieux, au bout de la troisième on commence à se trouver en terrain connu.

La quatrième chose est probablement reliée à la deuxième – « ça prend du temps ». J’ai une ode à faire à la craie et au tableau noir. Les nouvelles technologies nous ont apporté tout un tas de machins vachement chiadés, des vidéoprojecteurs, des tableaux numériques, et je crois que je vais même mettre le tableau blanc et les Velleda dans le lot. Au risque de passer pour une vilaine réactionnaire, tout ça ne vaut pas la craie et le tableau noir. Bon, OK, vert, le tableau, je concède ça. C’est plus long d’écrire une preuve au tableau que de sortir un Powerpoint (ou des slides Beamer, je suis pas sectaire dans mon rejet 😉 ) avec la preuve dessus. Donc ouais, on avance moins vite dans le cours, probablement. Mais ça laisse aussi le temps de suivre. Et, c’est très con, mais ça laisse aussi le temps de prendre des notes. Beaucoup de mes collègues de classe me disent qu’ils « préfèrent écouter que noter » (surtout que souvent, pour les cours au tableau, on a des polys qui sont en général d’excellente qualité). Pour moi, noter aide à rester concentrée, et au final à mieux écouter. Je griffonne aussi au crayon certains points de raisonnement qui seraient pas forcément évidents à la relecture. Bon, des fois, je me laisse des blagues pour les révisions, aussi – j’ai trouvé l’autre jour un joli « It’s a circle, OK? » à côté d’une figure de patatoïde. Ça m’a beaucoup fait rire. Ah, et quant au fait que ma hargne s’étende aux tableaux blancs : déjà, les feutres Velleda, ça marche jamais. En plus, des fois, ya un marqueur permanent qui vient se paumer dans le porte-feutres (et après on passe un temps dingue à repasser au feutre effaçable pour effacer). Et en plus, ça s’efface plus vite. J’ai appris à apprécier la pause induite par le nettoyage du tableau noir – la méthode « courante » chez nous est de faire deux passes, une avec un machin humide et une avec une raclette. Ça m’a vachement impressionnée la première fois que j’ai vu ça 😉 (oui, je suis très impressionnable) et depuis, je profite de la minute ou deux que ça prend pour relire ce qu’on vient de faire. Je trouve ça salutaire. Bref, le tableau et la craie, c’est la vie.

Et j’ai aussi appris à lire un article scientifique, du moins avec une méthode qui me convient à moi. En général, je fais une première passe très rapide pour avoir une idée de la structure de l’article, de quoi il parle, de la manière dont s’enchaîne la preuve principale, et j’essaie de voir s’il y a des trucs qui vont m’agacer - je commence à avoir des idées assez arrêtées sur les structures qui me facilitent ou pas la vie dans un article, et quand ça en dévie je râle un peu, même si je suppose que ces structures sont pas les mêmes pour tous. (Bon, il y a aussi des articles intrinsèquement pénibles à lire, il faut l’admettre.) Par « très rapide », j’entends entre une demi-heure et une heure pour un article d’une dizaine de pages.

Ma deuxième lecture est une lecture « d’annotations ». Je lis un peu plus en détail, et je mets des questions partout. Les questions sont en général de l’ordre du « pourquoi ? »  ou du « comment ? », sur des éléments de langage tels que « it follows that » (il suit de ce qui précède que), « obviously » (il est évident que), ou tous les trucs genre « par une simple application du théorème de Machin ». C’est aussi « relativement » rapide, parce qu’il y a beaucoup de signaux auxquels se raccrocher, et que je ne cherche pas encore à avoir une compréhension de tous les détails, mais à identifier les détails qui nécessitent que j’y passe un peu de temps pour les comprendre. Je note aussi les points qui me « gênent », c’est à dire les points où je ressens une espèce d’inconfort. C’est un peu difficile à expliquer, parce que c’est vraiment un « gut feeling », une intuition qui me dit « mmmh, là, ya un truc qui coince. Je sais pas quoi, mais ya un truc qui coince. » J’aime pas trop le terme d’intuition pour traduire « gut feeling », parce que c’est littéralement ça. Une espèce de malaise dans l’abdomen qui traduit l’inconfort.

Pendant la troisième lecture, qui est la plus longue, je m’attache à répondre aux questions de la deuxième lecture et à reprendre les calculs. Et à me convaincre, bien souvent, que oui, ce machin est bien une typo, et pas une erreur dans mon raisonnement ou mes calculs à moi. La quatrième lecture et les lectures suivantes continuent sur le même mode pour les questions auxquelles je n’ai pas répondu pendant la troisième lecture (et qui peuvent peut-être s’éclaircir entre temps).

J’estime que j’ai compris un papier quand j’ai répondu à l’immense majorité des questions posées en deuxième phase. (Et je me débrouille en général pour trouver quelqu’un de plus malin que moi pour celles qui restent en suspens). Mais même là… je sais que bien souvent, c’est pas encore parfait.

Le test ultime, c’est de préparer une présentation à propos du papier. Dans la série faites ce que je dis, pas ce que je fais, quand je fais ça, je prépare… des slides pour vidéoprojecteur. Parce que j’ai beau préférer, en tant qu’étudiante, un cours au tableau, je me rends bien compte que c’est beaucoup de boulot, et que faire une (bonne) présentation au tableau, c’est difficile. Un jour, j’essaierai – peut-être. Une fois que j’ai des slides (qui, en général, me permettent de re-débusquer quelques points obscurs), je tente de faire une présentation. Et là, on revient au « gut feeling ». Si ça bafouille, s’il y a des slides qui n’ont pas de sens, si la présentation ne se passe pas comme sur des roulettes, c’est qu’il y a probablement encore quelque chose derrière qui nécessite que j’y passe du temps.

Quand tout, finalement, finit par sembler « bien », le sentiment qui prévaut, c’est une espèce de soulagement mêlé de victoire. Je sais pas trop à quoi comparer ça. Peut-être aux gens qui font des dominos. Tu passes un temps dingue à mettre tes petits dominos l’un après l’autre, et je pense qu’au moment où le dernier tombe sans que le truc soit interrompu, ça doit être à peu près ce sentiment-là.

Évidemment, je peux pas me permettre de faire ça avec tout ce que je lis, ça prendrait trop de temps. Je sais pas s’il y a moyen d’accélérer le processus mais je pense pas que ce soit possible, au moins pour moi, de façon significative. Parce que j’ai aussi besoin de « laisser décanter » les choses. Il y a d’ailleurs pas mal d’hypothèses « fortes » sur le fait que le sommeil ait un impact important sur l’apprentissage et la mémoire ; je ne sais pas dans quelle mesure on peut étendre ça à mes histoires de compréhension, mais ça m’étonnerait pas que le cerveau en profite pour ranger et faire les connexions qui vont bien.

Du coup, c’est parfois assez frustrant de laisser les choses à un état de « compréhension partielle », surtout quand on ne sait pas exactement ce qui coince. Le « gut feeling » est là (et pas seulement à la veille de l’examen 🙂 ). C’est parfois ce qui me ferait tout laisser tomber : à quoi bon comprendre les choses à moitié ? Mais peut-être que la moitié, c’est mieux que rien du tout, quand on sait qu’il reste la moitié du chemin à parcourir. Et, parfois, quand on s’entête un peu, tout finit par cliquer ensemble. Et c’est un sentiment d’accomplissement que pas grand chose d’autre n’arrive à égaler.

Intuition mathématique

Je viens de commencer à rédiger un billet sur la complexité algorithmique, mais je me suis dit que celui-ci venait avant, parce que je ne suis pas à l’abri des tics de langages qui commencent à me venir : « intuitivement », « on voit bien que », « il est évident que ». Christophe m’a d’ailleurs fait remarquer que mon « ça me paraît assez clair » du billet sur les logarithmes (je crois que j’en ai au moins deux) n’était pas forcément des plus heureux. J’avais commencé par intituler ce billet « Compréhension, intuition et créativité », je crois que je vais me limiter au deuxième, parce que ça fait déjà un billet d’un fort beau gabarit ma foi.

J’essaie autant que possible, quand j’explique, d’éviter « l’argument d’intuition », parce que ça m’angoissait pas mal au début quand on me l’offrait et que, justement, je nageais pas mal à comprendre pourquoi c’était intuitif. Notons au passage que ça m’est encore arrivé l’autre jour en examen, de me vautrer sur le « pourquoi c’est intuitif ». Un truc qui me paraissait tellement lumineusement évident que j’en oubliais la raison profonde pour laquelle c’était évident. C’est assez agaçant quand on te le fait remarquer… surtout quand « on » est un examinateur. Mais je m’égare.

Un des articles les plus intéressants que j’ai lus sur le sujet est un article de Terry Tao, There’s more to mathematics than rigour and proofs (et oui, les plus observateurs remarqueront qu’il est en anglais 🙂 ). Il y distingue trois « stades » dans l’éducation mathématique :

  • le stade « pré-rigoureux » : on fait beaucoup d’approximations, d’analogies, et probablement plus de calculs que de théorie
  • le stade « rigoureux » : on essaie de faire les choses proprement, de façon précise et formelle, et on manipule des objets abstraits sans avoir forcément de compréhension profonde de ce qu’ils représentent (mais on les manipule correctement)
  • le stade « post-rigoureux » : on connaît suffisamment son domaine pour savoir quelles approximations et quelles analogies sont effectivement valides, on a une bonne idée rapidement de ce qu’un truc va donner quand on aura fini la preuve/le calcul, et on comprend effectivement les concepts qu’on manipule.

Je m’estime à peu près dans un mélange des trois niveaux 🙂 Je commence à avoir une certaine « intuition » (je reviendrai sur ce que je mets là-dedans), mais j’ai toujours autant de mal à mener un calcul proprement. Et, évidemment, ça dépend des domaines : dans mon domaine, je suis à peu près là ; si on me demande là tout de suite de résoudre des équadiff ou de faire de l’analyse qui tache, je vais probablement me sentir au stade pré-pré-rigoureux :)

Donc, de mon point de vue, les catégories sont évidemment plus fluides que ça, mais je crois que le message est le bon. Et qu’il faut pas paniquer quand la personne en face dit « il est évident/intuitif que » : c’est juste qu’elle a plus de pratique. Et qu’il est parfois difficile d’expliquer ce qui est devenu, avec la pratique, évident. Si je dis « il est évident que 2+3=5 », on sera probablement tous d’accord là-dessus ; si je demande « oui mais pourquoi 2+3=5 ? », on finira bien par me répondre, mais je m’attends à un blanc d’au moins quelques secondes avant ça. Je caricature un peu, mais je crois que c’est à peu près l’idée.

Dans le langage courant, l’intuition a quelque chose de magique, de « je sais pas pourquoi, mais je crois que les choses sont comme ci ou comme ça et qu’il va se passer ci ou ça ». J’ai tendance à me méfier pas mal de l’intuition dans la vie courante, parce que j’ai tendance à me méfier de ce que je ne comprends pas. En maths, la définition est à peu près la même : « je crois que le résultat va avoir cette gueule là, je sens bien que si je déroule cette preuve ça va marcher ». L’avantage de l’intuition mathématique, c’est qu’on peut la vérifier, comprendre pourquoi elle est juste, ou pourquoi elle est fausse. Dans mon expérience, l’intuition - juste - (ou ce qu’on met derrière ce mot) vient surtout avec la pratique, avec le fait d’avoir vu différentes choses, avec le fait d’avoir étudié pas mal, avec le fait de relier les choses les unes aux autres. Je pense que ce qu’on met derrière le mot « intuition », c’est le fait de relier quelque chose de nouveau (un nouveau problème) à quelque chose qu’on a déjà vu, et de faire ça correctement. C’est aussi le fait de reconnaître des « schémas » (j’utiliserais le mot « pattern » si j’écrivais en anglais). Dans le domaine de la complexité algorithmique, qui est le sujet du prochain billet en projet, c’est « je pense que cet algorithme va me prendre tant de temps, parce qu’au final c’est la même chose que celui-là qui est super connu et qui prend tant de temps ». Le truc, c’est que les associations ne sont pas toujours « conscientes » : on se retrouve à voir le résultat d’abord, et à l’expliquer après.

Ça n’empêche évidemment pas de se planter dans les grandes largeurs. Penser qu’un problème va prendre beaucoup de temps à résoudre (algorithmiquement parlant), alors qu’en fait il y a une condition qui le rend facile. Penser qu’un problème n’est pas très difficile, et se rendre compte qu’en fait il va prendre plus de temps que ce que l’on pensait. Enfin, en tous cas, à moi ça m’arrive toujours. J’estime le fait de me planter comme un progrès par rapport à l’étape précédente qui était « mais comment peut-on avoir une quelconque idée sur le sujet ? ».

Je ne sait pas comment se développe cette intuition. Je sais que la mienne est dans un bien meilleur état que ce qu’elle était il y a un an et demi. C’est suffisamment récent pour qu’il m’arrive encore de m’émerveiller sur le fait que des choses sur lesquelles je nageais à l’époque me paraissent maintenant assez naturelles.

C’est aussi suffisamment récent pour que je me rappelle l’angoisse de pas comprendre pourquoi ça peut être intuitif pour certaines personnes. Alors, promis, je vais essayer d’éviter. Mais j’aimerais bien que si jamais ça m’échappe vous me le fassiez remarquer, surtout si ça vous pose problème. Accessoirement, il y a de bonnes chances que si je dis « c’est intuitif », c’est parce que j’ai la flemme de partir dans des explications qui me semblent évidentes (mais qui ne le seraient peut-être pas pour tout le monde). Donc, voilà, je vais essayer de ne pas avoir la flemme 🙂