Journal P=NP démontré ?

Posté par (page perso) . Licence CC by-sa
Tags : aucun
20
30
mai
2013

Xinwen Jiang a publié sur le site de la Cornell University un papier nommé «A Polynomial Time Algorithm for the Hamilton Circuit Problem» qui impliquerait que P=NP est vrai.

«In this paper, we introduce a so-called Multistage graph Simple Path (MSP) problem and show that the Hamilton Circuit (HC) problem can be polynomially reducible to the MSP problem. To solve the MSP problem, we propose a polynomial algorithm and prove its NP-completeness. Our result implies NP=P.»

Pour mémoire le lien wikipedia sur sur ce problème dont la résolution impliquerait quelques changements dans à peu près tous les domaines scientifiques : http://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%3D_NP

Affaire à suivre, donc. Espérons qu'elle ait une autre fin que celle des neutrinos plus rapides que la lumière.

  • # Lien

    Posté par (page perso) . Évalué à 10.

  • # Des commentaires de chercheur ?

    Posté par (page perso) . Évalué à 10.

    Il y a à peu près cinq « démonstrations » par ans de ce théorème ou de sa négation. J'en ai même lu une ou l'auteur se basait sur le fait que R (l'ensemble des réels) est dénombrable (ce qui est évidemment faux).

    Est-ce que des chercheurs ont donné leur avis sur cette preuve ou es-tu simplement tombé dessus pas hasard ? Je crains qu'il soit trop tôt pour s'emballer, d'autant plus que le résultat démontré est celui auquel on ne s'attendait pas (et qui met toutes la sécurité basé sur la crypto asymétrique à la poubelle) !

    • [^] # Re: Des commentaires de chercheur ?

      Posté par (page perso) . Évalué à 1.

      Non, ça met la crypto sur RSA à la poubelle. Il me semble que les méthodes basées sur les courbes elliptiques résisteraient.

      • [^] # Re: Des commentaires de chercheur ?

        Posté par (page perso) . Évalué à 10.

        Si la vérification de la solution d'un problème est dans P (polynomiale) alors sa résolution est dans NP (car il peut être résolu dans P par un machine non déterministe d'où le nom NP) ; ça c'est la définition de NP.

        P=NP signifie donc que si on peut vérifier le résultat d'un problème rapidement alors on peut résoudre ce problème rapidement. Par exemple si le problème est la factorisation d'entier « Soit r un entier trouver deux entiers >1 tel que r=pq », Si je te donne la solution, un couple (p,q), vérifier que p * q = r se fait en tant polynomiale (on multiplie) donc la factorisation est dans NP et donc dans P !

        Il existe des problèmes que ne sont même pas dans NP (encore plus difficile). Non seulement tu mets 6 siècle à résoudre le problème, mais en plus le seule moyen de vérifier que la solution est bonne est de re-résoudre le problème !

        Les chiffrements asymétriques se basent sur le fait que l'on ne peut pas trouver en temps polynomiale la clé privée à partir de la clé publique. Considérons le problème « connaissant la clé publique, trouver la clé privée ». Calculer la clé publique à partir de la clé privée est rapide (sinon il faudrait 5 siècles pour générer le couple de clés) et donc on peut vérifier en temps polynomiale que la clé privée correspond à la clé publique.

        Ainsi puisque P=NP, résoudre ce problème se fait en temps polynomiale.

        Donc tous les chiffrements asymétriques sont foutus ! Et les chiffrements symétriques sont inutilisable seul en pratique. La seule solution serait la crypto quantique.

        • [^] # Re: Des commentaires de chercheur ?

          Posté par . Évalué à 1.

          Si la vérification de la solution d'un problème est dans P (polynomiale) alors sa résolution est dans NP (car il peut être résolu dans P par un machine non déterministe d'où le nom NP) ; ça c'est la définition de NP.

          Pour être précis, c'en est une caractérisation. La définition originale concerne les machines Non déterministes (d'où le N).

        • [^] # Re: Des commentaires de chercheur ?

          Posté par . Évalué à 5.

          J'ai entendu dire que ça pourrait résister quand même, pour plusieurs raisons:

          • polynomial n'implique pas rapide, si la vérification est en O(N) et que le cassage de la clé publique se fait en O(N10) (et pas mieux), et qu'on casse en un temps raisonnable (disons 1 jour) une clé de taille k, en prenant simplement une clé de taille 2*k il faudrait un peu plus de 2 ans pour casser la clé, ça devient plus raisonnable. Bon c'est pas aussi bien que d'avoir un algo exponentiel en face mais ça peut être pas mal à condition de renouveler souvent les clés.
          • la notation en O cache une constante, si la constante est très élevée pour l'algo de cassage il se peut que la solution polynomiale ne vaille pas la peine (il y a d'ailleurs des problèmes où il existe une solution polynomiale mais où les gens préfèrent la solution exponentielle parce qu'elle est plus rapide en pratique).

          Donc ça serait certes problématique, mais pas forcément la fin de la cryptographie asymétrique. On vivrait toujours dans la crainte qu'il existe un algo plus rapide que ceux qu'on connaît, et que quelqu'un le garde pour soi, mais cette crainte existe déjà aujourd'hui.

          • [^] # Re: Des commentaires de chercheur ?

            Posté par . Évalué à 3.

            J'ajouterais que P=NP nous dit juste qu'un tel algorithme existe… pas l'algorithme.

            • [^] # Re: Des commentaires de chercheur ?

              Posté par (page perso) . Évalué à 7.

              En pratique si. Pour cela on part d'un problème NP-Complet de référence, le problème SAT (cf Problème_SAT).

              Pour montrer que P=NP en générale (c'est ce qui est fait dans le papier du journal) on prends un problème, on montre que si il peut être résolu de manière polynomial alors SAT peut l'être (et donc par transitivité tous les autres problèmes NP). Ensuite on propose un algorithme de la classe P pour notre problème. Ce qui nous donne directement un algorithme de la classe P pour SAT.

              Maintenant prenons un autre problème NP. On peut le résoudre (par définitions de NP) par une machine de Turing non déterministe (c'est long à traduire, c'est chiant, mais ce n'est pas compliqué, d'ailleurs il doit exister un compilateur C vers machine de turing non déterministe). En très gros écrire un algorithme non déterministe c'est écrire un algorithme qui vérifie une solution (cf mon post précédent).

              Mais la preuve de la NP-complétude de SAT nous donne l'algorithme pour transformer le code polynomiale exécuté par la machine de Turing non déterministe en un problème SAT de même classe de complexité, et comme on sait résoudre SAT de manière polynomiale (sous réserve que P=NP) alors on a l'algo de la classe P.

              Donc pour ceux qui n'ont pas compris mes explication pas très claire, écrire un traducteur qui part d'un algo non déterministe (un algo qui vérifie la solution) et qui nous donne un code polynomiale est « simple ». En faire un qui propose un algo efficace — autre que des O(N25689) — est une autre paire de manche, mais si le théorème s'avère vrai, ce compilateur devrait apparaître rapidement.

        • [^] # Re: Des commentaires de chercheur ?

          Posté par (page perso) . Évalué à 1.

          Ainsi puisque P=NP, résoudre ce problème se fait en temps polynomiale.
          Donc tous les chiffrements asymétriques sont foutus

          Sauf si le temps en question reste extrêmement long.
          Cela implique que le calcul de départ est lui-même extrêmement long (mais moins), ce qui détruit l'intérêt de la chose. C'est bien ça ?

          • [^] # Re: Des commentaires de chercheur ?

            Posté par (page perso) . Évalué à 5.

            Le problème c'est que tu veux que le chiffrement soit instantané sur un smartphone (moins de 10s) mais coûteux sur une grappe de 100 machines puissantes (plus d'un ans). Donc les constantes doivent être vraiment moche ! C'est pas impossible certes.

            Et puis cela veut dire que toutes les discussion peuvent être considérée comme étant potentiellement en claire un an après.

            Par exemple je rentre mes identifiants sur https://linuxfr.org "username : cantor" "mot de passe : justinbieber" ; alors tu pourra décoder mon mots de passes en moins d'un an. Et si je ne l'ai pas changé depuis, alors tu auras accès à mon compte…

            Pour être honnête ce n'est pas ma spécialité, mais dans tous les cas ce résultat serait vraiment préoccupant (au moins à moyen terme) et nécessiterai de repenser en partie la sécurité.

            • [^] # Re: Des commentaires de chercheur ?

              Posté par . Évalué à -1.

              Non, car la connexion est chiffrée par chiffrement symétrique et la clé (qui change à chaque fois) est échangée par la méthode Diffie-Hellman.
              En gros chaque partie génère un nombre secret (que l'autre partie n'a pas besoin de connaître) et pour calculer la clé il faut connaître au moins un de ces deux nombres. La totalité de l'échange peut être transmis en clair sur le réseau, ça n'a aucune importance, quelqu'un l'ayant écouté ne sera pas en mesure de retrouver la clé.
              Le chiffrement asymétrique ne sert ici qu'a signer (pour empêcher une attaque mitm). La compromission des clés RSA ou autre ne compromet pas les communications précédentes.

              (Bon évidemment ce n'est pas valable si la méthode Diffie-Hellman est foutue en l'air aussi.)

      • [^] # Re: Des commentaires de chercheur ?

        Posté par . Évalué à -2.

        Ce n'est pas parce qu'on prouve que P = NP que d'un coup, RSA tombe. Car même si on sait ça, on n'est pas plus avancé pour trouver un algo en temps polynomial capable de trouver une clé privée à partir de sa clé publique.

        Or, ça fait quand même un bout de temps qu'on essaie de le trouver, cet "algo miracle", en supposant que P = NP..

    • [^] # Re: Des commentaires de chercheur ?

      Posté par . Évalué à 6.

      Ton commentaire va très bien avec ton pseudonyme.

    • [^] # Re: Des commentaires de chercheur ?

      Posté par (page perso) . Évalué à 2.

      « J'en ai même lu une ou l'auteur se basait sur le fait que R (l'ensemble des réels) est dénombrable (ce qui est évidemment faux). »

      Est-ce qu'il ne s'agissait pas plutôt de l'ensemble des nombres à virgule flottante codés sur un nombre fixe de bits ?

    • [^] # Re: Des commentaires de chercheur ?

      Posté par . Évalué à -10.

      " J'en ai même lu une ou l'auteur se basait sur le fait que R (l'ensemble des réels) est dénombrable (ce qui est évidemment faux) " (…)

      o_O
      " la liste des entiers naturels est infinie, car chacun d'entre eux a un successeur, c'est-à-dire un entier qui lui est immédiatement supérieur " (…)
      ( Source : Entier naturel - Wikipédia )

      Donc les réels… (Niveau collège)

      • [^] # Re: Des commentaires de chercheur ?

        Posté par . Évalué à 9.

        Dénombrable, pas finis.

        Les entiers naturels tu peux les compter, ils se comptent tout seul, ils sont dénombrables, les paires d'entiers naturels aussi par exemple :

        0 (0,0)
        1 (1,0)
        2 (0,1)
        3 (2,0)
        4 (1,1)
        5 (0,2)
        6 (3,0)
        7 (2,1)

        Tu vois que tu peux associer à chaque entier naturel une paire d'entiers naturels, et réciproquement. C'est très contre intuitif, mais il existe une correspondance un à un entre les éléments d'un ensemble, et ceux d'un ensemble "plus gros". Pour te donner une image, si tu prend d'un coté une ficelle (en 1D donc) et un carrelage (en 2D) tu peux associer chaque carreaux une portion de ficelle si tu fait parcourir la ficelle sur les carreaux, ligne par ligne. Certes la ficelle sera beaucoup plus longue que le coté du carrelage, mais elle est infinie, ça marche.

        Pour les réels, ça ne marche pas, cf la fameuse diagonale de cantor
        https://fr.wikipedia.org/wiki/Argument_de_la_diagonale_de_Cantor#La_non_d.C3.A9nombrabilit.C3.A9_des_r.C3.A9els
        (jette un œil, c'est très accessible, et très « graphique » comme démonstration)

        La notion de successeur est aussi importante, qu'est-ce que le successeur d'un réel ? c'est celui qui vient juste après ? mais aussi près qu'on le prenne, on peut toujours en prendre un entre les deux.
        Puis c'est d'autant plus trompeur, que l'ensemble des rationnels lui, est dénombrable. alors qu'il ressemble beaucoup à celui des réels dans l'intuition qu'on s'en fait.

        Please do not feed the trolls

  • # Ma référence perso sur le sujet : pas de nouvelle

    Posté par . Évalué à 6. Dernière modification le 30/05/13 à 22:07.

    Perso ma référence baromètre sur le sujet et ce qui tourne autour est ce très technique blog de théoricien http://rjlipton.wordpress.com/ qui ne mentionne pour l'instant à priori pas du tout ce résultat, donc faut pas s'emballer (j'avais lu pleins de trucs intéressant lors de la précédente pas preuve ayant fait du bruit il y a quelques années sur ce blog)

  • # Bon, mais cet article ?

    Posté par (page perso) . Évalué à 2.

    À la fin de l'article, l'auteur de dit-il pas avoir utilisé son algo rithme polynomial contre des dizaines de millions de graphes, et d'avoir toujours eu les bons résultats ?
    Si son algo n'est pas correct, c'est tout de même une sacré heuristique, non ?

    • [^] # Re: Bon, mais cet article ?

      Posté par (page perso) . Évalué à 2.

      Ça ne veut rien dire.

      Un peu la flemme de lire l'article, à vrai dire, mais il y a pas mal de possibilités :
      - des problèmes qui ne sont compliqués à résoudre que dans des rares cas
      - la distribution de ses essais n'est pas franchement bien faite et ne sont pas du tout représentatifs de l'ensemble des problèmes
      - l'algo n'est pas totalement polynomial :D (de mémoire, il faut qu'il soit polynomial en la taille de l'instance codée en binaire, et non codée en unaire — exemple bateau : trouver les diviseurs d'un nombre est polynomial quand tu codes en unaire mais exponentiel quand tu codes en binaire)

      • [^] # Re: Bon, mais cet article ?

        Posté par . Évalué à 4.

        Sachant que la taille d'un nombre représenté en unaire est exponentielle par rapport au binaire, c'est bonnet blanc et blanc bonnet

        Please do not feed the trolls

      • [^] # Re: Bon, mais cet article ?

        Posté par . Évalué à 2.

        Un autre cas possible est que la réduction d'un problème NP-complet à son problème ne soit en fait pas polynomiale, ou pas exhaustive.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.