Le blog de Balise

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

Publié le 30 juin 20139 novembre 2013 par Balise1 commentaire

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

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

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

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

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

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

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

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

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

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

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

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

Probabilités – Partie 2

Publié le 24 juin 201314 février 2019 par Balise2 commentaires

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

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

Donc, aujourd’hui, c’est ~~raviolis~~variables 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 ? 🙂

Décès de Michel Laclos

Publié le 20 Mai 2013 par Balise1 commentaire

Je viens d’apprendre, via le Twitter de Bernard Pivot, le décès de Michel Laclos, auteur prolifique de grilles de mots croisés.

Il y a des gens qu’on associe toujours à d’autres, et j’associe toujours Bernard Pivot et Michel Laclos à mes grands-parents. On a fait quelques fois la dictée de Pivot, il y a longtemps avec la retranscription de la Voix du Nord (je crois me souvenir que c’était Mamie qui dictait, et nous on grattait 😉 ), et plus tard avec l’enregistrement cassette du magnétoscope… Il fut un temps où j’avais une meilleure orthographe qu’aujourd’hui, ça m’agaçait toujours de faire des fautes, même sur des mots que je n’avais jamais lus ou entendus ! (Maintenant ça m’agace toujours de faire des fautes que je ne devrais pas laisser passer. C’est un autre débat.)

Quant à Michel Laclos, je crois bien avoir toujours entendu parler des « mots croisés de Michel Laclos », difficiles mais rigolos (Ou rigolos parce que difficiles…). Les dictionnaires – standards et de mots croisés – étaient rangés dans le salon, et visiblement fréquemment utilisés. Y compris par moi, d’ailleurs, j’ai probablement passé un certain temps dedans, je trouvais ça marrant de classer les mots par nombre de lettres. Je me souviens aussi des stylos beiges avec une gomme au bout, des hypothèses écrites avec une main légère pour pouvoir les effacer plus facilement, du papier glacé des grilles.

Et je me souviens de Papi qui racontait souvent en souriant qu’il avait fini par trouver un mot sur une définition particulièrement vicieuse de la grille du moment. Et moi je voyais ça avec une certaine admiration, parce que même les « faciles », « rho, j’aurais jamais trouvé » 🙂

Bref, l’annonce de ce décès m’a fait un peu bizarre. Monsieur Laclos, vous avez probablement touché beaucoup de monde avec vos grilles, et vous en avez probablement touché bien plus indirectement…

Murphy m’en veut personnellement

Publié le 20 avril 2013 par Balise6 commentaires

Je vois pas d’autre explication. Et je m’excuse pour ma série d’articles d’info théorique, j’ai pas eu le temps de m’y replonger ces derniers temps. Mais j’y pense. Bref.

Il y a trois semaines, on s’est fait réveiller à 5 heures du matin par un boucan phénoménal, et des trombes d’eau qui semblaient venir de… D’un peu au-dessus du bâtiment, et seulement d’un côté de l’appartement. À peu près comme ça, mais vu du bâtiment d’à côté et du 5e étage. Passées les premières suppositions (phénomène météo vraiment stupide, barrage qui a pété) (il était 5h du mat, ok ?), on finit par nous dire qu’une grosse canalisation a pété dans la rue. 60 cm, suffisamment de bars pour monter jusqu’au 6e étage, et paf, ça pète devant la porte de mon immeuble. Bon. Il se trouve qu’on a un petit balcon sur l’appart, et que ce petit balcon est entouré d’un mur. Pas d’une grille, non, d’un mur. Avec un petit trou de 2-3cm pour laisser évacuer l’eau. De pluie. Parce que le petit trou d’évacuation, il fait pas le malin face à un torrent de flotte qui embarque avec lui des morceaux de route. (On a plus tard retrouvé un pavé de 2,5kg sur le balcon.) Le balcon s’est rempli aux 80cm de sa hauteur en quelques minutes.

Évidemment, derrière le balcon, il y a une porte fenêtre. Sinon c’est pas très utile d’avoir un balcon. Les joints de la porte fenêtre, ils ont pas non plus longtemps fait les malins devant les 80cm de flotte du balcon. (Ils font techniquement pas vraiment les malins quand il pleut beaucoup non plus). L’eau a commencé à rentrer. C’est à peu près à ce moment là que Pierre m’a dit « habille-toi » (encore une fois, 5h du mat), « on se casse ». On a récupéré au passage nos sacs à dos (contenant portefeuilles, divers machins et… laptops), Pierre a tenté de colmater vaguement la porte entre le salon et le reste de l’appart avec ce qui traînait (nos peignoirs, essentiellement), et on est descendus. Par l’escalier, normalement. Au fur et à mesure de la descente, de plus en plus d’eau – évidemment, tout le monde a les mêmes balcons, et tous les appartements commencent à déborder. L’arrivée au rez-de-chaussée reste une image assez terrifiante pour moi. On a déboulé là-dessus :

Avec les vagues, la porte qui battait, et le bruit de l’eau qui continuait à se déverser dans la rue.

On a pris notre courage à deux mains, et on est sortis du bâtiment (pas par cette porte là, ça aurait probablement été dangereux, mais il y a une porte derrière qui était au sec).

Notons que l’eau froide à hauteur des genoux, quand il fait nuit et qu’il fait froid, ben ça fait froid. Et là, on sort du bâtiment, et il se met à NEIGER. Dru. On se promène un peu autour du pâté de maisons, on finit par retourner du côté de chez nous pour voir l’eau se déverser dans la rue.

On a fini par voir le niveau d’eau de la « fontaine » décroître progressivement. Il a fallu 1h20 pour réussir à couper l’eau. (C’est apparemment pas évident de couper l’eau sur une conduite de cette taille, si on veut éviter les problèmes en cascade en amont…) Il est estimé que 15 millions de litres d’eau se sont déversés sur l’immeuble et sur la route.

On s’est finalement fait ramasser par un bus de la protection civile, ils nous ont filé du café, des fringues sèches le temps que les nôtres passent au sèche-linge, et un petit-déjeuner. On est restés avec eux jusque 16h, à peu près – c’est encore eux qui savaient le mieux ce qu’il se passait. On a été très soulagés quand ils nous ont annoncé que la statique du bâtiment n’avait pas souffert, et qu’on allait pouvoir au moins repasser chez nous.

Vers 16h, on a pu retourner à l’appartement. Les gens de la voirie étaient en train de remettre du bitume au-dessus de la canalisation réparée, et les équipes de rénovation commençaient à s’organiser. Ils nous avaient dit de nous préparer au fait que tout serait ruiné et que l’eau coulait depuis les plafonds. La montée des 5 étages s’est faite avec une grosse boule dans l’estomac. Heureusement, nos voisins du 6e n’avaient pas de balcon, n’ont pas eu d’eau chez eux, et n’ont donc pas dégouliné chez nous. Les dommages sont restés limités au sol. Nos voisins des étages inférieurs ont été moins chanceux.

Le niveau d’eau est monté à 20cm dans le salon (là où il y avait le balcon), et quelques centimètres dans le reste de l’appartement. Quand on est montés, ils avaient déjà pompé toute l’eau. On a été très soulagés de voir que, comparativement, peu de choses avaient souffert. Mes bouquins étaient restés au-dessus du niveau de l’eau, et nos jeux de plateau… aussi 🙂 Les ordinateurs semblaient ne pas avoir pris l’eau dans leurs boîtiers. (Depuis, Pierre a diagnostiqué que sa carte mère n’avait pas survécu…)

Ça fait donc un peu plus de trois semaines que notre appartement n’est plus habitable. Entre temps, il a été vidé (faire l’inventaire et évaluer l’année et le prix d’achat de tout ce qui traînait a été épique…) ; quelques meubles ont déjà fini à la benne (l’agglo, ça aime pas l’eau. Les canapés non plus.), le reste est dans un entrepôt quelque part en banlieue. Maintenant, on attend que l’entreprise de rénovation fasse son boulot. À l’heure actuelle, les appartements de l’immeuble ont plus ou moins tous été vidés et débarrassés de leurs planchers (les planchers flottants, c’est VIEUX, nous on avait un plancher À VAGUES !) et du crépi/de la tapisserie des murs. On est raisonnablement sûrs que le bâtiment ne va pas être détruit, mais on n’a pas vraiment d’information officielle sur le sujet. On n’a pas non plus d’information sur le temps que ça va prendre. Probablement encore plusieurs mois ; on espère que le nombre de mois sera limité à 2 ou 3, mais on ne sait pas.

Jusqu’ici, on a squatté chez des copains qui ont eu la riche idée de partir en vacances au moment où on avait besoin d’un endroit pour se poser. On a aussi les clés d’un petit meublé pas trop loin (c’est petit, c’est cher, et les types qui ont fait l’ameublement et la déco fument des arbres par paquets de 12, mais ya un toit, un lit, et un accès à Internet.)

On déménage là-bas aujourd’hui, on doit avoir trois ou quatre allers-retours à faire pour trimbaler tout notre bordel. Il faisait 25°C avant-hier. Ce matin, il neige.

Probabilités – partie 1

Publié le 11 mars 201310 février 2019 par Balise12 commentaires

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 🙂

Bon, je fais quoi maintenant ?

Publié le 4 mars 20139 novembre 2013 par Balise6 commentaires

Bon bon bon. Je commence à avoir fait un peu le tour de ce que je dont je voulais absolument parler. Pour récapituler un peu :

un article d’introduction à l’informatique théorique
quelques notions de complexité algorithmique, partie 1, et de complexité algorithmique, partie 2, pour lesquelles j’ai aussi eu besoin de parler de logarithmes
la question P est-il égal à NP, un petit détour par le problème SAT, et la notion de problèmes NP-complets
deux billets « méta » sur l’intuition mathématique et la compréhension mathématique (j’en ai un troisième de prévu à l’occasion sur la créativité, mais il infuse encore un peu)

Maintenant, qu’est-ce que vous voulez ? J’ai plusieurs pistes, mais c’est des pistes assez différentes, alors je sais pas trop 🙂 du coup, je me dis que je peux aussi vous demander votre avis. Dans l’ordre dans lequel ça me vient à l’idée :

Je peux faire un peu de théorie des graphes. Un truc que j’avais en tête était d’expliquer comment chercher un plus court chemin dans un graphe, par exemple.
Je peux continuer sur les problèmes NP-complets. Dans les trucs que j’ai en tête, expliquer la réduction pour prouver que la 3-colorabilité est NP-complète.
Je peux parler de SAT. Là j’ai deux trucs faisables : je peux parler des algorithmes pour 2-SAT (qui sont simples, choupis et polynomiaux) ou d’algorithmes pour 3-SAT (et plus) qui peuvent être aussi simples à expliquer, mais moins choupis et vachement moins polynomiaux. Je reste sur le côté théorique de la question, par contre, parce que j’ai pas la moindre idée de ce qui se fait côté pratique et que je vais dire des conneries.
Si je parle d’algos 3-SAT, je peux probablement étendre sur ce que je fais en ce moment ; ça risque d’être vachement poilu cependant.
Je peux causer géométrie algorithmique, aussi, la géométrie c’est cool. Je peux parler de triangulations et de Voronoï, par exemple.
On peut faire des probas, dans la série des trucs cools ; si je traite le point suivant je commencerai probablement par ça.
Je peux causer algorithmes aléatoires, à quoi ça sert, comment ça marche, tout ça.
Je peux causer de problèmes « classiques » difficiles et parler d’approximation (par exemple, je suis un voleur dans un musée, je cherche à remplir mon sac à dos avec des objets de taille et de valeur variées, comment je fais pour maximiser la valeur totale de ce que j’embarque pour que ça tienne dans mon sac à dos ?)

Heu, voilà, ce sont quelques suggestions. Si vous en avez d’autres, n’hésitez pas non plus ; je ne garantis rien parce qu’écrire sur un sujet que je ne connais pas prend nécessairement beaucoup, beaucoup plus de temps et que je croule pas sous le temps ces temps-ci ; mais il est toujours possible que j’aie oublié des trucs dans ce que je pourrais traiter sans trop de problème :)

Quant aux gentils lecteurs qui auraient des idées sur certaines questions qui compléteraient mes idées à moi, ya toujours moyen de négocier si ça vous dit de venir en parler ici 😉

Donc, qu’est-ce que vous voulez ? (Et il me serait agréable que vous répondiez à cette question et que vous ne me colliez pas un vent phénoménal, merciiiii 😉 ).

Problèmes NP-complets

Publié le 1 mars 20139 novembre 2013 par Balise5 commentaires

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

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

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

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

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

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

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

The Hardness of the Lemmings Game, or Oh no, more NP-Completeness Proofs – un papier qui parle du caractère NP-complet de Lemmings
A Survey of NP-Complete Puzzles – un papier qui recense tout un tas de résultats sur le sujet
Gaming is a hard job, but someone has to do it! – qui parle de jeux vidéo, dont Boulder Dash, Doom et Lode Runner. Et Puzzle Bobble.

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.

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 :

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

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

Publié le 25 février 20139 novembre 2013 par Balise15 commentaires

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 ? »

Publié le 15 février 20139 novembre 2013 par Balise21 commentaires

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 :

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

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 :

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 :

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

Publié le 14 février 20139 novembre 2013 par Balise10 commentaires

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.

	Ja dans Y’a encore des gens sur…
	Balise dans Y’a encore des gens sur…
	Natacha dans Y’a encore des gens sur…
	Balise dans Y’a encore des gens sur…
	krysztophe dans Y’a encore des gens sur…

Flattr:

Flattr:

Flattr:

Flattr:

Flattr:

Flattr:

Flattr:

Flattr:

Flattr:

Flattr: