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 😉

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

  1. Pour ajouter en rigolo, il me semble indispensable de montrer la célèbre photo des inventeurs du RSA (hint pour ceux qui connaissent pas : la blagounette est sur le tableau noir).

  2. Un résultat que je trouverais ‘achement rigolo, ce serait que N = NP soit équivalent à l’axiome du choix (j’aimerais beaucoup voir un équivalent algorithmique du découpage de Banach-Tarski) ou un autre axiome tueur d’intuitions du genre, ou qu’il soit indépendant de tous les axiomes connus.

    « Voilà, tu sais comment P est par rapport à NP, ça t’avance bien, hein ? »

  3. Il faut trouver un algorithme de complexité P dont le complémentaire en P est de complexité L et donc P ne serait pas égal à NP…

  4. Je n ai qu un mot : Super. Enfin quelqu un qui expose des exemples compréhensibles. Merci à toi, ça m’a beaucoup aidé. Je pense que t y a mis du temps mais je pense aussi que tu as aidé beaucoup de monde. Merci, biz, à la prochaine session………..

  5. salut,
    J’ai pondu un algo qui me résous tous les problèmes du sac à dos de type 0/1 que je lui ai proposé jusqu’à présent mais je ne voit pas du tout en quoi ça a force de prouver qu’il sait tous les résoudre..
    En gros résoudre un problème np-complet en temps polynomial et cela même un très grand nombre de fois n’a aucune valeur démonstrative.

    Qu’en penses-tu ?

    1. Absolument. D’ailleurs, on résout des instances de SAT tous les jours (et heureusement, beaucoup de choses en dépendent !). Pour autant qu’on sache, si P != NP, la quantité d’instances d’un problème qui sont réellement difficiles à résoudre est très faible… Mais oui, c’est la différence fondamentale entre l’instance du problème et le problème lui-même.

  6. Bonjour,
    Tout d’abord merci pour l’exposition de votre point de vue.
    J’ai une question, dans cette formule inconnue de P=nP ou P#nP il s’agit bien de problème potentiellement resolvable avec une machine de Turing? Soit un ordinateur fonctionnant en code binaire?
    Cordialement
    Kell adrian

    1. On parle effectivement bien du modèle de Turing ici (et des modèles divers qui lui sont équivalents). Notons que ça n’a pas grand chose à voir avec « un ordinateur fonctionnant en code binaire » – il est assez facile de montrer, par exemple, qu’une machine de Turing avec un alphabet de taille constante est équivalente à une machine de Turing binaire.

      1. Je me posai la question car Si pour definir précisement les problèmes P et NP nous utilisons la théorie de comptabilité sous le modèle de machines de Turing, et que nous admettons que ces machines fonctionne avec le système binaire et donc ne « comprennent » que ce langage la?
        Si tel est le cas pouvons nous admettre que
        P=0 ou P=1
        Et egalement NP=0 ou NP=1 ?

        Pour moi il ne s’agit que de compréhension et de vitesse de compréhension donc d’évolution
        Lorsque nous sommes en présence de P=0 il n’y a pas de problème à démontrer, lorsque P=1 le problème est déjà annalisé, compris et n’est deja plus un « probleme » pourl’ordinateur.
        La nuance avec NP c’est qu’il sont plus complexe.. dans un cryptage complexe SAT l’ordinateur doit effectuer toute les possibilité pour que les variantes soit égales à 1 donc utiliser des bits donc prendre du temps…
        Chaque problème NP fini par être un problème N qui fini par ne plus être un problème une fois l’évolution terminé ( et ça marche pour l’évolution générale egalement)
        Je pensais au cryptage SAT .. ramener chaque valeurs à des bits permettrai de connaître le temps pour résolver le cryptage. J’ai écrit un truc mais je suis naze en ordi…impossible de l’appliquer

      2. Alors.
        On peut effectivement admettre que les machines ne « comprennent » que le binaire, ça c’est pas un problème.
        Par contre, on ne peut pas admettre que P=0 ou que P=1, ni que NP=0 ou que NP=1 – parce que P et NP ne sont pas des variables auxquelles on peut attribuer des valeurs, mais des classes de problème (et un « problème N » n’existe pas).
        Du coup, la suite de votre commentaire n’a pas vraiment de sens.

      3. Désolé pour les bêtises que je peu dire…J’ai essayé de comprendre.
        Si cela ne vous gêne pas j’aimerai débattre un peu de ce sujet, je vais forcément dire des aberrations et je m’en excuse d’avance.

        Ce que je ne comprend pas c’est que dans les problèmes P et NP, on recherche un résultat pour que chaques variables soit égale à 1 je pensai donc que la résolution de P et NP était juste 1 et que la recherche de cette résolution était lié a la recherche du nombres du résultat pour que toutes les variables soit égales à 1.
        J’admmettais que la différence entre P et NP est N la durée de compréhension plus longue de P.
        je me disais avant allumer la lumière était un problème NP puis quelqu’un à compris, ils ont créé l’ampoule et canalisé l’électricité et mis en application le problème qui est devenu P facile pour tout le monde même sans comprendre son fonctionnement exact appuyer sur un bouton permet la lumière tout le monde le sais au point que ce nest plus un probleme. NP serai egal à des bits puis à la solution 1 donc du temps du à la résolution des variables pour que cela fonctionne, pour devenir un problème simple P que tout le monde résout en appuyant sur l’interrupteur donc qui est aussi résolu donc égale à 1, si l’ampoule pète ou qu’il n’y a plus de jus cela équivaut à nouveau à un problème facile qui requiert P donc recherche de solution pour passer de 0 à 1, et si c’est tout le pays qui manque de jus cela sera pour certain un problème NP à nouveau et pour ceux qui ont appris/compris le fonctionnement ce serai un problème P construction d’une eolienne par exemple, la construction prendra le temps qu’il faut pour que P soit égal à 1 à nouveau. ..
        Même si je suis bien à côté de la plaque je vous remercie d’avoir pris le temps de répondre à mes interrogations qui sait pour le moment P= ou # de NP est un NP avec un peu de temps il deviendra peu être P…

  7. Je me disais juste que dans le problème du voyageur de commerce le chemin à parcourir est à déterminé en fonction de chaque position de ville par rapport à la ville de départ. .. et si on prenait la ville de départ qu’on imagine le meridien de Greenwich et l’équateur sur cette ville on peu recalculer chaques positions de ville par rapport à la ville de départ créer une fonction entre chaque ville et la ville d’origine et en déduire une seule fonction…
    En recréant un point de vue par rapport à la ville d’origine et non par rapport au monde…

  8. Je ne veut pas la lune, vous commander non plus mais juste un mots ou deux l’histoire de me dire « c’est une idee » ou « c’est une abheration »…

  9. Alors. Je comptais bien répondre, mais je savais que ça allait me prendre un peu de temps, du coup j’ai un peu procrastiné, et… bref.
    C’est effectivement, comme vous le dites, assez à côté de la plaque 😉

    « Ce que je ne comprend pas c’est que dans les problèmes P et NP, on recherche un résultat pour que chaques variables soit égale à 1 je pensai donc que la résolution de P et NP était juste 1 et que la recherche de cette résolution était lié a la recherche du nombres du résultat pour que toutes les variables soit égales à 1. » Pas mal de confusion ici, y compris peut-être une confusion entre le problème SAT et les classes de problème P et NP. Car c’est cela qu’il ne faut pas oublier : P et NP sont des _classes_ de problèmes, pas des problèmes eux-mêmes. La question « P est-il égal à NP » est de savoir si les deux classes sont équivalentes, c’est-à-dire « est-ce que tous les problèmes qui sont dans la classe P sont également dans la classe NP » (ça, c’est vrai et ça découle de la définition des classes en question) et « est-ce que tous les problèmes qui sont dans la classe NP sont également dans la classe P » (ça, c’est la question à 1 million de dollars à laquelle la plupart des mathématiciens ont tendance à croire à la réponse négative).

    Vous avez à nouveau un « pour que P soit égal à 1 à nouveau » en fin de paragraphe qui n’a aucun sens. P n’est pas une variable.

    Pour les histoires de voyageur de commerce, c’est également plus compliqué que ça – et vous restreignez également le problème considéré – en toute généralité, il n’y a aucune notion de distance ou de métrique dans le problème du voyageur de commerce, il n’y a qu’un graphe avec des arcs pondérés, de sorte que la notion de position par rapport à un nœud donné n’a pas forcément de sens non plus, du moins pas dans le sens où on l’entend en géographie.

    Bref, tout cela me paraît malheureusement plus du côté de « c’est une aberration » que « y’a de l’idée »…

    Si vous souhaitez creuser ce genre de sujet, peut-être qu’un bouquin introductif sur le sujet pourrait aider. Le texte « usuel » Introduction to Algorithms de Cormen, Leiserson, Rivest et Stein, dont il existe une traduction en français (Introduction à l’Algorithmique, chez Dunod) est probablement un peu brutal (et accessoirement un pavé); il existe probablement des sources plus abordables (peut-être du côté de ce qu’il se fait pour l’enseignement de l’algorithmique niveau lycée/licence/prépa ?), mais il ne m’en vient pas à l’esprit à froid.

    1. Ce que je ne comprend pas c’est que P et NP sont des classe de problèmes donc représentent des problémes….et que quelques soit la classe de problème d’un problème l’ordinateur ne pourra « comprendre » que si il fait des tonnes de calcul pour que toutes les variables ou autre du problème soit égal à 1 car pour lui il y a que deux réponses possible 0 et 1. 0 non compris et 1 compris. Et quelques soit le temps de calcul ce sera q’une succession de 0 et de 1 du point de vue d’un ordinateur.
      L’évolution permet un fonctionnement par étape qui evite d’ aller à des classe de problème NP directemnt, mais plutôt de passer par une succession de P et c’est ce qu’il ce passe pour l’ordinateur il résout plein de P contenu dans NP pour réussir à résoudre NP.

      1. Pardon pour la derniere phrase ce serai plutot :il faut plein de problème de classe P pour résoudre un problème de classe NP qui devient du coup un problème de classe P et ainsi de suite..

        C’est une question de temps pour nous, une succession d’evolution pour la planete et une succession de 0 et de 1 pour l’ordinateur.

        A l’échelle de la planète nous étions un problème de classe P mais notre temps d’évolution plus rapide que la sienne nous classe au rang NP et créer un déséquilibre. Ce déséquilibre ce traduit par un climat s’accélèrant ( le temps reel pour la planete s’exprime pour nous grâce au climat)car les impacts de l’homme sur terre sont plus important et provoque donc une multitude de problèmes de classe P qui pour le moment sont un un problème de classe NP. Plus il y a de problème de classe P plus la résolution de ce problème arrivera vite pour la planete..elle passera à 1.. l’évolution le climat changera vite et brusquement et par ce fait résoudra tout les problèmes de classe P en même temps..plus d’humain problème résolu.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s