TPA : Théorème des cinq couleurs

Aujourd’hui, c’est coloriage. Je vais déjà commencer par vous montrer un petit jeu : ça s’appelle Map, c’est tout con : le jeu vous donne une carte rectangulaire avec des zones à colorier, et quelques couleurs déjà placées ; il faut colorier les autres de façon à ce que deux voisins n’aient pas la même couleur. Allez-y, allez jouer un peu avec, c’est rigolo 😛 La question théorique derrière ce petit jeu est la suivante : quel est le nombre minimal de couleurs nécessaires pour pouvoir colorier n’importe quelle carte de ce type ? Peut-être que vous vous souvenez, mais j’ai déjà un peu parlé de problèmes de ce genre là : quand j’ai parlé de P vs NP, j’ai parlé de colorabilité de graphes, et de décider si un graphe donné pouvait être colorié avec un nombre donné de couleurs. La question du nombre minimum de couleurs peut revenir à poser la question précédente plusieurs fois : « et avec 2 couleurs, ça passe ? non ? et avec trois ? non plus ? et avec quatre ? ah, cool. » Là, normalement, j’ai deux objections dans la salle. La première, c’est : « minute papillon, tu parlais de cartes et là tu me parles de graphes, c’est pas pareil, si ? ». La deuxième, c’est « heu, dis voir, demander si un graphe peut être colorié avec trois couleurs, on a vu dans le P vs NP que c’était pas trivial comme question… donc on fait quoi, surtout qu’il y a peut-être beaucoup de nombres à considérer ? ». Il se trouve que la première objection permet de répondre à la deuxième. Pour répondre à la première objection, je vais faire un petit dessin. Voilà le petit dessin. map   Le petit dessin en question, il est fait comme suit :

  • j’ai commencé par dessiner la carte – la structure en noir ;
  • j’ai ajouté un point dans chaque zone de la carte (les points rouges) ;
  • j’ai relié deux points (avec les traits rouges) si les zones correspondantes étaient voisines.

NORMALEMENT j’ai vérifié ma construction, mais si elle est bancale (si j’ai des traits en trop ou en pas assez), merci de me le signaler 🙂 Et là, que voit-on apparaître en rouge sous nos yeux ébahis ? Un graphe. Pas n’importe quel graphe, d’ailleurs : il s’agit d’un graphe planaire, c’est à dire qu’on peut le dessiner sur une feuille de papier sans que deux arcs se croisent. J’ai parlé de graphes planaires dans un billet de blog précédent : Planarité, mineurs et donuts. Là, il va falloir que vous me fassiez confiance sur quelques points. Primo, la construction ci-dessus est toujours possible. Deuzio, ça donne toujours un graphe planaire. Tertio, ce graphe planaire est unique pour une carte donnée : il a toujours le même nombre de sommets, et les arcs sont toujours les mêmes. Et c’est là qu’on répond à la deuxième objection. Oui, dans le cas général, décider si un graphe peut être colorié avec 3, 4, 5 ou 12 couleurs est difficile (au stade actuel de nos connaissances). Par contre, dans le cas particulier des graphes planaires, on sait plus de choses. Plus précisément, on connaît le théorème suivant, appelé « théorème des 4 couleurs » :

Tout graphe planaire peut être colorié avec au maximum 4 couleurs.

Et, comme corollaire au point précédent, je peux colorier une carte avec quatre couleurs (il suffit de faire ma petite construction là-haut, de colorier le graphe résultant, et de colorier chaque zone avec la couleur du sommet en question – rappelons que dans le cas qui nous intéresse, un coloriage est valide si deux sommets reliés par un arc n’ont pas la même couleur.) Un petit aparté: je parle de « cartes » ici, mais c’est pas vraiment applicable directement « dans la vraie vie ». Le problème principal, c’est que certains pays ne sont pas « connectés ». Et si on colorie une carte du monde, on s’attend à ce que, par exemple, la Guyane soit de la même couleur que la France. Ce qui ajoute des arcs entre la zone « France » et les zones « Brésil » et « Suriname », et qui risque fort de nuire à la planarité du graphe correspondant. Fin de l’aparté, revenons à nos moutons. Donc, si j’ai un graphe planaire, je peux répondre directement à la question « est-ce que ce graphe peut être colorié avec k couleurs » par « oui », dès que k est supérieur ou égal à 4. La preuve du théorème des quatre couleurs est… compliquée. J’en parlerai dans un prochain billet, mais il faut que je me documente encore un peu avant sur le sujet 🙂

Un résultat intéressant est que pour trois couleurs, même dans le cas « graphe planaire », le problème reste NP-complet ! (C’est un résultat de Stockmeyer en 1973, dans un article intitulé « Planar 3-colorability is polynomial complete », qui 40 ans plus tard est toujours planqué en tant qu’article payant à l’ACM. Mais je digresse.) Donc, pour 3 couleurs, c’est dur à décider, pour 4 couleurs, on sait qu’on peut le faire, mais c’est dur à prouver. En revanche, le théorème suivant est relativement simple à prouver :

Tout graphe planaire peut être colorié avec au maximum 5 couleurs.

J’ai dit que c’était relativement simple à prouver, et donc je vais le faire. Ça va quand même être probablement un peu long, donc accrochez-vous, et je vais essayer de faire preuve de pédagogie 🙂

J’ai besoin d’un premier résultat pour ma preuve :

Tout graphe planaire contient au moins un sommet de degré au plus 5.

Le degré d’un sommet, c’est le nombre d’arcs qui y sont connectés. Comme un arc connecte exactement deux sommets, si je fais la somme des degrés de tous les sommets, j’obtiens deux fois le nombre d’arcs (parce qu’un arc donné est compté exactement deux fois, une fois à chacune de ses extrémités). Maintenant, je vais vous demander d’admettre encore un truc, c’est qu’on connaît le nombre maximal d’arcs d’un graphe planaire, en fonction de son nombre de sommets, n : il y a au plus 3n-6 arcs, dès qu’il y a plus de deux sommets (comme on me l’a fait remarquer en commentaire). Je pourrais aussi le démontrer, mais ça implique encore un résultat intermédiaire, et ce billet va finir par être vraiment beaucoup trop long (dit-elle au bout de deux pages). Comme j’ai au plus 3n-6 arcs, la somme des degrés de tous les arcs d’un graphe planaire est inférieure ou égale à 6n-12. Par conséquent, il y a au moins un sommet de degré au plus 5 : si ce n’est pas le cas, la somme des degrés de tous les arcs est supérieure ou égale à 6n (6 arcs, multipliés par n sommets), et ce n’est pas possible pour un graphe planaire.

Revenons à nos moutons initiaux : on veut maintenant démontrer que tout graphe planaire peut être colorié avec au maximum 5 couleurs. On va faire un raisonnement par récurrence sur le nombre de sommets du graphe. J’ai interrompu la rédaction de ce billet pour aller faire un billet sur le raisonnement par récurrence, allez le lire si le terme ne vous est pas ou plus clair 🙂 Donc, on commence par traiter l’hypothèse de base. Si mon graphe n’a qu’un seul sommet, je peux le colorier avec au maximum 5 couleurs : j’en choisis une pour mon sommet, et voilà.

Maintenant, je suppose que l’hypothèse de récurrence suivante est vraie : tout graphe planaire à (n-1) sommets peut être colorié avec au maximum 5 couleurs. Le but du jeu est maintenant de déduire, à partir de ça, que tout graphe planaire à n sommets peut être colorié avec au maximum 5 couleurs. Pour ça, on considère un graphe à n sommets, n’importe lequel (si je démontre que ça marche pour n’importe quel graphe, je montre que ça marche pour tous les graphes). Par le résultat intermédiaire que j’ai prouvé au-dessus, le graphe à n sommets étant planaire, il a un sommet de degré inférieur ou égal à 5, qu’on va appeler v dans la suite pour aller vite. On peut prendre v, et le retirer temporairement (on retire aussi tous les arcs qui y sont connectés). Le graphe sans v est un graphe planaire à (n-1) sommets. Donc, on peut le colorier avec au maximum 5 couleurs. Maintenant, on remet v (et les arcs qu’on a retirés aussi) : on obtient un graphe à n sommets dont (n-1) sommets sont coloriés avec au maximum 5 couleurs, et un sommet, v, n’a pas encore de couleur.

Là, on a deux possibilités. Si les voisins de v (les sommets auxquels v est connecté) utilisent moins de 5 couleurs, on peut utiliser une des couleurs non utilisées pour colorier v, et le graphe initial est colorié avec au maximum cinq couleurs.

Sinon, si on prend une représentation plane du graphe planaire, on est dans la situation suivante :

fiveneighbors Je n’ai dessiné ici que six sommets, v et ses cinq voisins. Le graphe peut contenir plus de sommets et plus d’arcs, mais il contient forcément cette structure.

Sur ma représentation plane, je choisis arbitrairement un voisin de v, je l’appelle v1, et je numérote les autres dans le sens des aiguilles d’une montre (v2 à v5). Les sommets v1 à v5 sont de cinq couleurs différentes. Je vais maintenant prouver que je peux soit colorier v1 et v3 de la même couleur, soit colorier v2 et v4 de la même couleur.

Je regarde d’abord v1 et v3, et plus précisément je m’intéresse au sous-graphe colorié avec les couleurs de v1 et de v3, c’est-à-dire que je prends tous les sommets de la couleur de v1 (gris, sur la figure) et tous les sommets de la couleur de v3 (bleu, sur la figure), et tous les arcs du graphe initial qui relient ces sommets entre eux. Un exemple sur un petit graphe :

subgraphÀ droite, j’ai représenté le sous-graphe du graphe de gauche en ne prenant que les sommets bleus et gris (j’ai supprimé les sommets rouges et violets, et les arcs qui y étaient attachés). Sur ma figure, j’ai quatre sommets entre lesquels j’ai des chemins (une suite d’arcs qui me permettent de passer de l’un à l’autre), et un sommet qui n’a de chemin vers aucun autre.

Si je ne regarde que les sous-graphe bleu/gris de mon graphe initial, j’ai deux possibilités : soit v1 et v3 ne sont plus connectés, soit ils le sont encore ; et par « connectés », j’entends qu’il y a un chemin entre v1 et v3. S’il n’y a pas de chemin, v1 et v3 sont dans des composants différents (un composant, c’est un ensemble de sommets qui sont reliés les uns aux autres par des chemins). Dans ce cas là, je regarde le composant qui contient v3 (il se peut que ce soit v3 tout seul, mais sinon c’est un ensemble de sommets bleus et gris qui ont tous un chemin connecté à v3). Dans ce composant-là, le fait que les sommets soient bleus ou gris est arbitraire : je peux inverser les deux couleurs sans que ça ait un impact sur le fait que le graphe est correctement colorié. Si je ne fais ça que dans ce composant là, v1 (qui n’est pas dans composant en question) reste gris, et v3 (qui était bleu) devient gris. Maintenant, je peux remettre le « reste » du graphe (les sommets rouges, violets, verts, et le sommet v qui n’est pas encore colorié) : comme je n’ajoute pas de sommets bleus ou gris, le coloriage reste valide. Et j’ai « libéré » le bleu pour mon sommet v : donc, je peux colorier v en bleu. La vie est belle.

Enfin, presque. Parce qu’il se peut aussi que v1 et v3 soient dans le même composant « bleu/gris ». Donc là, si j’inverse le bleu et le gris, ben je me retrouve avec v1 en bleu, et v3 en gris, et je peux toujours rien faire avec v. Donc, il faut trouver une autre astuce.

Je regarde maintenant le sous-graphe composé des sommets coloriés avec les couleurs de v2 (rouge) et v4 (vert) : je retire tout ce qui n’est pas rouge ou vert du graphe, et je regarde ce qui reste. Si v2 et v4 ne sont pas dans le même composant rouge/vert, je peux inverser le rouge et le vert dans le composant de v4. v2 reste rouge, v4 devient rouge, et je peux colorier v en vert. Là, j’ai peut-être quelqu’un qui me dit « oui, mais si v2 et v4 sont aussi dans le même composant, tu as le même raisonnement et donc le même problème que pour le composant bleu/gris ! ». Oui, mais. Regardons un peu ce qui se passe sur la figure. Comme v1 et v3 sont dans le même composant bleu/gris (sinon, on n’aurait pas besoin de regarder ce qui se passe dans le composant rouge/vert), il y a un chemin entre v1 et v3 composé de sommets bleus et gris.

bluegreypath

Si je veux faire un chemin composé de sommets verts et rouges entre v2 et v4 (ce qui est la condition pour que v2 et v4 soient dans le même composant rouge/vert), ça bloque : soit je dois croiser l’arc entre v et v3, soit je dois croiser un des arcs du chemin bleu/gris entre v1 et v3. Et comme mon graphe est plan… ben j’ai pas de croisement entre mes arcs. Donc, v2 et v4 ne peuvent pas être dans le même composant, donc je peux bien inverser les couleurs du composant de v4, et colorier v en vert.

J’ai donc regardé tous les cas possibles pour mon graphe, et dans tous les cas, je peux colorier le sommet v de façon valide. Donc, si un graphe avec (n-1) sommets peut être colorié avec au maximum 5 couleurs, alors un graphe avec n sommets peut être colorié avec au maximum 5 couleurs, ce qui termine mon étape de récurrence et donc la preuve du théorème des cinq couleurs. Ouf.

J’avais initialement prévu de parler du théorème des 4 couleurs plus en détail dans ce billet, mais je crois que je vais arrêter là pour ne pas fumer plus de neurones de mon lectorat (en espérant qu’il y en ait quand même une partie qui soit arrivée jusqu’ici…). Comme d’habitude, pour les questions, typos, remarques, etc., c’est dans les commentaires que ça se passe 🙂

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 😉