Journal P != NP : la preuve

Posté par (page perso) .
Tags : aucun
15
9
août
2010
Cher journal,

En ces temps estivaux, alors que tout le monde est a la plage, la recherche avance ! Vinay Deolalikar, chercheur chez HP, affirme avoir trouvé une preuve (de 100 pages quand même) que P != NP, rien que ca. La preuve s'appuierait sur tout un tas de domaines (statistiques, théorie des graphes, etc.)

Cette annonce, aussi intéressante soit-elle, est a relativiser puisque l'article n'a pas encore été reviewé. Il est d'ailleurs étonnant que l'article ait été proposé par email, et non soumis à un journal ou une conférence. Il faudra donc attendre un peu que des experts évaluent l'article avant qu'éventuellement, ce chercheur puisse recevoir le Millenium prize (1M$ quand même) récompensant cette preuve.

L'impact de cette preuve (si elle est correcte) reste toutefois minime, il s'agirait surtout de la confirmation d'une conjecture admise par la plupart des spécialistes

Le papier
  • # Mais ké kidi?

    Posté par . Évalué à 10.

    De quoi parle ce journal? C'est quoi P et NP? En quoi cette découverte est importante? Quel est le domaine d'application?
    Bon, c'est bien, on sait qu'un gars à réussi a le prouvé, bien qu'il n'ai pas encore publié...

    Tu peu donner plus de détail pour les incultes comme moi?
    • [^] # Re: Mais ké kidi?

      Posté par . Évalué à 9.

    • [^] # Re: Mais ké kidi?

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

      C'est un des problème majeurs de la théorie de la complexité et donc de l'Informatique. Je pense que la page Wikipedia expliquera mieux que moi: http://fr.wikipedia.org/wiki/Th%C3%A9orie_de_la_complexit%C3(...)
      • [^] # Re: Mais ké kidi?

        Posté par . Évalué à 2.

        Ha ben déjà, c'est un poile plus claire!
        Bon, ok, j'ai pas tout compris, mais au moins, maintenant, je comprend vaguement à quoi ça correspond...
        • [^] # Re: Mais ké kidi?

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

          Désolé, en écrivant (vite fait) ce journal je n'ai pas pensé au public. Moi qui pensait qu'ici on ne trouvait que des gens civilisés (ie. des gens ayant suivi au moins un cours de théorie de la complexité).
          mea culpa.
          • [^] # Re: Mais ké kidi?

            Posté par . Évalué à -1.

            J'ai beau avoir de l'humour, ton insulte passe difficilement...
            • [^] # Re: Mais ké kidi?

              Posté par . Évalué à -8.

              C'est parce que t'es con.
              • [^] # Re: Mais ké kidi?

                Posté par . Évalué à 2.

                Merci, tu peux développer?
                A part ça, tu as quelque chose à ajouter au débat?
                • [^] # Re: Mais ké kidi?

                  Posté par . Évalué à 1.

                  Ouais, je peux.

                  Il ne t'a absolument pas insulté.
                  Détends toi.
                  • [^] # Re: Mais ké kidi?

                    Posté par . Évalué à 7.

                    Perso, j'ai considéré la réponse de François Trahay comme une insulte pour les gens qui n'ont pas compris ce qu'il voulait dire (il faut dire qu'il est très clair dans sa dépêche...)

                    Relation commune que je remarque souvent: Dès qu'on est pas le niveau requis, y'a toujours Dr quelque-chose ou Pr. de-flamby qui vous regardent de haut en vous insultant d'inculture.
                    • [^] # Re: Mais ké kidi?

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

                      En relisant ma réponse, c'est vrai qu'elle peut paraître insultante, ce qui n'était pas mon intention. Je voulais juste dire qu'en écrivant ce journal, je n'ai pas pensé a ceux qui n'ont pas suivi un cursus en informatique (la théorie de la complexité étant généralement enseignée dans la plupart de ces cursus).

                      Désolé si ma réponse vous a choqué.
                    • [^] # Re: Mais ké kidi?

                      Posté par . Évalué à 4.

                      Je pense que justement il bat vraiment sa coulpe.

                      Du coup, ce que vous prenez pour une insulte, je le prends comme une façon amusante de souligner plus avant son erreur de manque de clarté avec lequel nous sommes tous d'accord lui y compris.

                      (j'ai trouvé plus agressif http://linuxfr.org/comments/1150670,1.html par rapport à http://linuxfr.org/comments/1150669,1.html et les horaires respectifs).


                      Heureusement l'ensemble des DLFPiens semble moins porté sur le politiquement correct.
                      • [^] # Re: Mais ké kidi?

                        Posté par . Évalué à -1.

                        Parce que ça : [http://linuxfr.org/comments/1150667,1.html] c'est pas agressif des fois?
                        Je répond de manière polie à une insulte directe. Dit ce que tu veux, c'est toi qui as dépassé les bornes, et entre gens civilisés, c'est inacceptable.
                        • [^] # Re: Mais ké kidi?

                          Posté par . Évalué à -4.

                          Non, ce n’est pas agressif. C’est une manière détournée de te dire « tu as mal interprété le message original », ou encore en:GIGO
                  • [^] # Re: Mais ké kidi?

                    Posté par . Évalué à 2.

                    Il ne t'a absolument pas insulté.

                    Toi, par contre, tu l'as clairement fait.

                    Et, dans le cas présent, ce n'est pas parce que c'est du second degré que c'est plus fin. Désolé.
            • [^] # Re: Mais ké kidi?

              Posté par . Évalué à 3.

              Blague dans le groin, j'ai fait plus qu'un cours sur le domaine et dès que j'ai vu NP, j'ai compris qu'on parlait complétude, par contre, comme il est plus qu'admis que P != NP (c'est à dire que les profs ne font pas allusion au fait que ce n'est pas clairement démontré), je comprenais mal aussi...
              • [^] # Re: Mais ké kidi?

                Posté par . Évalué à 3.

                marrant dans mes cours c'était pas annoncé comme acquis, qu'il y avait toujours une prime qui courrait pour celui qui arriverait à démontrer que P=NP, et que jusqu'à présent tous ceux qui s'étaient penché dessus n'avaient pas réussi.

                Par ailleurs on a aussi fait la distinction entre un problème NP et un NP Complet.

                Il ne faut pas décorner les boeufs avant d'avoir semé le vent

                • [^] # Re: Mais ké kidi?

                  Posté par . Évalué à 2.

                  et pas de petite place pour les p approx ?
                  • [^] # Re: Mais ké kidi?

                    Posté par . Évalué à 3.

                    maintenant que tu le dis, si, en effet. :D

                    Ah comme ça remonte à loin tout ça, entre 6 et 8 ans. De bons souvenirs (et de bonne notes aussi).

                    Il ne faut pas décorner les boeufs avant d'avoir semé le vent

                • [^] # Re: Mais ké kidi?

                  Posté par . Évalué à 2.

                  La prime vaut aussi si on démontre P != NP
                  • [^] # Re: Mais ké kidi?

                    Posté par . Évalué à 2.

                    C'est pourtant facile : P ≠ NP, sauf si N=1. /o\

                    (Pataper, je sors tout seul. :-)
                    • [^] # Re: Mais ké kidi?

                      Posté par . Évalué à 4.

                      C'est faux. Contre exemple : P = 0, N = 2.

                      Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

                      • [^] # Re: Mais ké kidi?

                        Posté par . Évalué à 1.

                        oui mais non.
                        Parce que si P = NP, essayer de trouver une valeur de N tel que P=NP reviens essayer de résoudre P/P=N, et donc lorsque P=0, N ne peut pas être défini.

                        Alors il est comment mon rattraprages aux branches avec les ongles ?
                        (c'est jeudi soir, j'ai le droit).
    • [^] # Re: Mais ké kidi?

      Posté par . Évalué à 8.

      En gros : P, c'est l'ensemble des problèmes que l'on peut résoudre en temps polynômial (i.e. dont le temps de résolution est majoré par une fonction polynômiale de la taille des paramètres), et NP ceux que l'on peut résoudre en temps exponentiel (exemple : à partir d'une expression logique à N variables, trouver des valeurs de vérité qui satisfont l'expression).

      On a donc l'inclusion P c NP, mais l'on se demande si l'inclusion est stricte ou s'il s'agit d'une égalité. Dans le second cas, cela signifie qu'il est possible de traiter tout problème de complexité exponentielle en temps polynômial (en réduisant le problème à un autre problème par exemple). Cela aurait pour conséquence d'affaiblir de nombreux protocoles de chiffrement, signatures, etc. qui se basent sur le fait que "casser la clé" revienne à résoudre un problème NP particulier (pour lequel on a encore aucun algorithme en temps polynômial).
      Mais si l'inclusion est stricte, ça nous donne une garantie sur la sûreté des algorithmes de chiffrement/déchiffrement : si l'attaque se fait par cassage de clé, elle se fera en temps exponentiel. Il suffit donc de calibrer la taille de la clé pour que le temps nécessaire à la casser soit supérieur à sa durée de vie.
      • [^] # Re: Mais ké kidi?

        Posté par . Évalué à 9.

        Non. P est l’ensemble des problèmes que l’on peut résoudre en temps polynomial sur une machine déterministe, NP est l’ensemble des problèmes que l’on peut résoudre en temps polynomial sur une machine non-déterministe.
      • [^] # Re: Mais ké kidi?

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


        En gros : P, c'est l'ensemble des problèmes que l'on peut résoudre en temps polynômial (i.e. dont le temps de résolution est majoré par une fonction polynômiale de la taille des paramètres), et NP ceux que l'on peut résoudre en temps exponentiel (exemple : à partir d'une expression logique à N variables, trouver des valeurs de vérité qui satisfont l'expression).


        Pour être un peu plus précis, les problèmes NP sont des problèmes qui peuvent être résolus en temps polynomial avec une machine non-déterministe.

        Ça veut dire que le problème peut être compliqué a résoudre avec une machine déterministe (factoriser un grand nombre n par exemple), mais que une fois qu'on a trouvé la solution, on peut vérifier en temps polynomial que la solution est correcte (vérifier que p.q = n par exemple).
      • [^] # Re: Mais ké kidi?

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

        Ah non. NP veux dire non-déterministique polynomial. Ce qui signifie l´ensemble des problèmes soluble en un temps polynomial sur une machine d´états non déterministique (Cela n´existe pas en pratique. Mais les ordinateurs quantiques arrivent).

        Donc il en pratique, il faut un temps plus que polynomial pour résoudre un problême appartenant à NP (et pas à P) Mais il existe des problèmes solubles en un temps exponentiel qui n´appartiennent pas à NP.
        • [^] # Re: Mais ké kidi?

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

          En fait même les gens civilisés ne sont pas d'accord entre eux ^^
        • [^] # Re: Mais ké kidi?

          Posté par . Évalué à 6.

          En parlant d’ordinateurs quantiques, je ne sais pas si tu voulais dire qu’un ordinateur quantique peut résoudre un problème NP en temps polynomial, mais ce n’est absolument pas sûr.
          En fait, pour les ordinateurs quantiques, il y a le même genre de problèmes que pour P et NP, mais en ce qui concerne la classe en:BQP (bounded-error quantum polynomial time, la classe des problèmes solubles en temps polynomial par un ordinateur quantique avec une erreur arbitrairement faible).
          Par exemple, on sait que la factorisation de nombre premiers est dans BQP (grâce au fameux algorithme de Shor), mais comme il n’est pas prouvé que ce problème de factorisation n’est pas dans P, cela ne prouve pas que BQP est strictement plus grand que P.
          En l’état actuel, on peut juste affirmer qu’on connaît un algorithme efficace pour factoriser des nombres premiers sur un ordinateur quantique, et pas sur un ordinateur classique.
          • [^] # Re: Mais ké kidi?

            Posté par . Évalué à 5.

            Factoriser des nombres premiers ?
            Fastoche avec cet algorithme en O(0) :

            def factorisepremier (int n)
            return ensemble_vide


            Par contre pour factoriser *en* nombre premier c'est un peu plus dur ;)

            BeOS le faisait il y a 15 ans !

            • [^] # Re: Mais ké kidi?

              Posté par . Évalué à 2.

              Ton algo est juste faux. Je propose le patch suivant :

              -return ensemble_vide
              +return [n]

              Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

              • [^] # Re: Mais ké kidi?

                Posté par . Évalué à 2.

                et pour patcher le patch:

                -return n
                +return [1, n]

                certes, 1 n'est pas premier, mais ils divise quand même n.
            • [^] # Re: Mais ké kidi?

              Posté par . Évalué à 2.

              Oui, bien sûr, je ne dois pas être très réveillé encore.
              Mais ça n’enlève rien au reste du commentaire.
      • [^] # Re: Mais ké kidi?

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

        Pour apporter une précision, pour un problème NP, on peut vérifier la solution en temps polynomial (encore faut-il l'avoir).
      • [^] # Re: Mais ké kidi?

        Posté par . Évalué à 4.

        "Il suffit donc de calibrer la taille de la clé pour que le temps nécessaire à la casser soit supérieur à sa durée de vie."

        À noter une particularité intéressante, c'est que le temps d'exécution de ton programme de cassage de clé est majoré par une fonction exponentielle, ce qui ne veut pas dire que le temps total d'exécution pour trouver une solution le sera.
        Si la bonne clé est la première testée par ton programme (par exemple, si le mot de passe est "password" et que tu le testes en premier, au pif...), elle est trouvée immédiatement ;)
      • [^] # Re: Mais ké kidi?

        Posté par . Évalué à 9.

        Je ne suis pas expert, mais la logique m'oblige à te contredire:
        Ce n'est pas parce que NP != P que les algorithmes "de sécurité" ont maintenant une garantie:
        On sait juste qu'il est possible qu'ils soient aussi sûrs que prévus, alors que dans le cas contraire, il est impossible qu'ils soient sûrs.

        Conclusion: On peut toujours continuer à chercher des algos P pour décoder tout ce bordel.
        Ou bien j'ai rien compris?
        • [^] # Re: Mais ké kidi?

          Posté par . Évalué à 2.

          en fait ça va dépendre du type de problème; certains sont dit NP-complet; si mes cours sont encore bon, ces problèmes sont équivalent, et un résoudre un seul en temps polynomial reviendrait tous les résoudre et à démontrer P=NP.

          On sait démontrer qu'un problème est NP-Complet, on sait démontrer qu'un problème est dans P (quand on a la solution), par contre pour le reste, il y a comme qui dirait un flottement

          Il ne faut pas décorner les boeufs avant d'avoir semé le vent

          • [^] # Re: Mais ké kidi?

            Posté par . Évalué à 4.

            Par ailleurs NP-Complet ne veut pas dire impossible dans le cas moyen.
            Le problème de 3-coloration d'un graphe est NP-Complet mais, en moyenne, il requiert 197 operations.
            Oui, 197, quelque soit la taille du graphe, i.e. un O(1).

            Pour les histoires de securité il faut donc faire des études probabilistes et plein de trucs compliqués.
          • [^] # Re: Mais ké kidi?

            Posté par . Évalué à 3.

            Quasiment tout les problèmes NP-chiants sont déjà résolus, c'est leur résolution en complexité polynomiale qui n'est pas encore trouvé.

            Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

  • # Il dit qu'il est pas d'accord.

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

    >> L'impact de cette preuve (si elle est correcte) reste toutefois minime,

    On doit pas avoir la même définition de « minime » dans nos dictionnaires respectifs.
    Et « la plupart des spécialistes » n'admet pas "P != NP", je ne crois pas non. Je pense que « la plupart des spécialistes » n'a pas d'opinion publique sur la question, c'est prendre un risque trop élevé (et qu'il faut savoir justifier aussi).
    • [^] # Re: Il dit qu'il est pas d'accord.

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

      D'après un sondage ( [http://en.wikipedia.org/wiki/P_%3D_NP_problem#cite_note-poll(...)] ) auprès de la communauté scientifique, une majorité de spécialistes pense que P!=NP.

      Je ne dis pas que ces spécialistes parieraient leurs bourses la dessus. Ce qui est sur c'est que si il s'avère que P=NP, la plupart des algo utilises en crypto posent problème.
    • [^] # Re: Il dit qu'il est pas d'accord.

      Posté par . Évalué à 3.

      Euh, minime... bôf.
      La résolution de ce problème plane un peu comme une épée de damoclès au-dessus de nos têtes depuis des années, quand même. Tout le monde se fait un peu pipi dessus en se disant que si 'P = NP', c'est la fin du monde...
      Si 'P = NP' alors tous nos algorithmes de chiffrage de données sont bons à jeter, puisque le déchiffrage à algorithme connu se fait en temps polynômial. Ajoute à ça l'arrivée imminente (ou presque) des processeurs quantiques, et tu obtiens bien la fin du monde...

      Mais ouf,... P != NP.
      'fin bon, d'un autre côté, bon nombre de mathématiciens ont pu faire passer des théorèmes dont la preuve était fausse, et qui ont été annulés seulement quelques siècles plus tard... Pour être réavérés encore un siècle plus tard...
      Théorème 22 : plus y'a de pages, plus y'a de fautes probables. En 100 pages de démonstration, t'as le temps d'en faire, des fautes (j'irai pas vérifier, j'ai pas le level).
      • [^] # Re: Il dit qu'il est pas d'accord.

        Posté par . Évalué à 2.

        ha non tous les algos de chiffrement ne tombent pas, le one time pad par exemple reste parfaitement sur. Son seul soucis est qu'il nécessite une clé de la longueur du message.

        Il ne faut pas décorner les boeufs avant d'avoir semé le vent

        • [^] # Re: Il dit qu'il est pas d'accord.

          Posté par . Évalué à 4.

          Un autre algo de chiffrement qui reste tres efficace, et qui ne depend pas de la taille du message, est le schwizerdeutsch , c'est extremement efficace au point que des fois meme la personne chiffrant le message ne peut pas le dechiffrer quand il lui est renvoye.
        • [^] # Re: Il dit qu'il est pas d'accord.

          Posté par . Évalué à 1.

          Le one time pad n'est pas un "bon" algorithme de chiffrement parce qu'il suppose qu'il y a eu accord préalable sur la clef de chiffrement entre les 2 parties (ou échange sécurisé), et donc le chiffrement dépend de la sécurité de l'échange.
          Maintenant, le chiffrement/déchiffrement étant linéaire à clef connue, c'est clair que P != NP n'influera pas sur la complexité du problème.
          • [^] # Re: Il dit qu'il est pas d'accord.

            Posté par . Évalué à 5.

            Le one time pad n'est pas un "bon" algorithme de chiffrement parce qu'il suppose qu'il y a eu accord préalable sur la clef de chiffrement entre les 2 parties (ou échange sécurisé), et donc le chiffrement dépend de la sécurité de l'échange.

            Tout comme AES ou autres... C'est un algo symétrique.
            • [^] # Re: Il dit qu'il est pas d'accord.

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

              C'est vrai que le One-time-pad et AES nécessitent un échange de clés préalable.

              La différence, c'est la taille de la clé, avec AES elle est relativement petite. Avec un one-time-pad, la clé fait la taille du message. Donc si on a réussi a s'échanger une clé de taille N de manière sécurisée, pourquoi on se ferait chier a utiliser le one-time-pad pour s'échanger le message ?

              Cela dit, le One-time-pad peut être utile dans certains cas (par exemple pour le téléphone rouge http://fr.wikipedia.org/wiki/T%C3%A9l%C3%A9phone_rouge ).
              • [^] # Re: Il dit qu'il est pas d'accord.

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

                Donc si on a réussi a s'échanger une clé de taille N de manière sécurisée, pourquoi on se ferait chier a utiliser le one-time-pad pour s'échanger le message ?

                Par ce que à un instant T tu as la possibilité de faire un échange de manière sûre mais que tu n'a pas l'information à transmettre et que à un instant T+1 tu n'a plus cette possibilité mais que tu as l'infos.

                Imagine James Bond, au début du film il est dans les locaux du MI6 et il peut récupérer un CDrom avec la clé, ensuite il part chez le méchant et récupère les plans de l'étoile de la mort, à ce moment la il peut les chiffrer et les envoyer à Q sans avoir peur que les russes en profitent.

                Dans tous les cas, en général plus la clé est grande, plus le système est sûr. Le one-time-pad te donne une borne sur la taille maximale de la clé nécessaire pour chiffre un message unique.
                • [^] # Re: Il dit qu'il est pas d'accord.

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

                  C'est bien pour ca que je dis :
                  Cela dit, le One-time-pad peut être utile dans certains cas (par exemple pour le téléphone rouge http://fr.wikipedia.org/wiki/T%C3%A9l%C3%A9phone_rouge ).

                  Le cas que tu proposes est typiquement le cas du téléphone rouge. On s'échange des mallettes avec les prochaines clés a utiliser. Ensuite on n'a plus qu'a utiliser une clé différente a chaque message. C'est efficace, mais on ne peut pas l'utiliser dans la vie de tous les jours (genre pour sécuriser une transaction bancaire).

                  A noter que si le one-time-pad est sûr, il repose sur le fait que seuls les 2 communicants connaissent la clé. Donc si quelqu'un réussi a faire une copie de la mallette, il peut décoder tous les messages.

                  A première vue, ca ne change rien par rapport aux autres algo (AES, etc.), mais du fait du protocole d'échange de clés, la durée de vie d'un ensemble de clés est élevée. Par exemple, on n'échange pas une mallette a chaque fois qu'on veut envoyer un message, on en échange une par mois. Donc on augmente le risque d'interception.

                  Je ne retrouve plus les références, mais il me semble que c'est le genre de chose qui se faisait pendant la seconde guerre mondiale. Les bateaux/sous-marins partaient en mer avec les codes a utiliser les 30 prochains jours. Du coup quand un bateau était capturé et qu'on pouvait récupérer le carnet avec les codes, et bien on pouvait décoder plein de messages.
                  • [^] # Re: Il dit qu'il est pas d'accord.

                    Posté par . Évalué à 2.

                    Je ne retrouve plus les références, mais il me semble que c'est le genre de chose qui se faisait pendant la seconde guerre mondiale. Les bateaux/sous-marins partaient en mer avec les codes a utiliser les 30 prochains jours. Du coup quand un bateau était capturé et qu'on pouvait récupérer le carnet avec les codes, et bien on pouvait décoder plein de messages.

                    Ben en principe non. Lorsqu'une clé du bloc a été utilisée, elle est détruite. Si tu trouves le bloc, tu auras la possibilité de décrypter les messages futurs tant que le bloc n'aura pas été révoqué.

                    Par ailleurs, chaque bateau/sous-marin emportait son propre bloc: ce n'est pas parce que tu obtiens celui d'un bateau que tu pourras décoder tous les messages de tous les autres bateaux.

                    Enfin, c'est ce que j'avais compris de la lecture de l'excellent /cryptonomicon/.
                    • [^] # Re: Il dit qu'il est pas d'accord.

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

                      Oui mais les bateaux ont besoin de déchiffrer les messages envoyés depuis la terre/les autres bateaux. Donc ces carnets contenaient bien les clés de déchiffrement à utiliser. En récupérant un carnet, on pouvait donc déchiffrer les messages suivant jusqu'à ce que le carnet soit révoqué.
                    • [^] # Re: Il dit qu'il est pas d'accord.

                      Posté par . Évalué à 3.

                      Ben en principe non. Lorsqu'une clé du bloc a été utilisée, elle est détruite. Si tu trouves le bloc, tu auras la possibilité de décrypter les messages futurs tant que le bloc n'aura pas été révoqué.
                      C'est pire que ça!
                      Si le bloc est réutilisé, tu peux casser les deux messages SANS connaitre le bloc.
                      L'OTP c'est du xor du bloc et du message.
                      m1 XOR bloc = c1
                      m2 XOR bloc = c2

                      maintenant
                      c1 XOR c2 = (m1 xor bloc) XOR (m2 xor bloc)
                      = m1 xor m2

                      Bon donc déjà ce n'est plus du tout sur comme m1 et/ou m2 ne sont pas aléatoire il peut y avoir des attaques dessus sans soucis, et si on en vient à connaitre un des messages non chiffré, on retrouve l'autre sans soucis.

                      http://fr.wikipedia.org/wiki/One_Time_Pad#Probl.C3.A8me_de_l(...)
                      • [^] # Re: Il dit qu'il est pas d'accord.

                        Posté par . Évalué à 3.

                        Je pense que par "bloc réutilisé", il veut parler de l'utilisation d'une autre clé du bloc. (donc que vous avez une différence de vocabulaire ;-) )

                        Je pense que ce qui est échangé, c'est une "clé" de longueur donnée, couvrant plus de N messages de longueur moyenne m bits. Le bloc est donc un ensemble de N*m bits.

                        Pour le premier message, tu utilises les m_1 premiers bits (où m_i est la taille réelle du message i), pour le 2, les bits (m_1+1) à (m_1+m_2) ... François parle de l'interception des N*m bits, et de l'utilisation de sous-ensembles successivements, mais pas de la réutilisation du même bit.

                        (par contre, il reste un problème dans ce que je décris, comment peut-on savoir si le message que l'on reçoit est le message x ou x+n ? Parce qu'on peut avoir perdu un message, du coup on ne sait pas où commencer. Bon, on pourrait commencer par donner l'offset en fait)

                        Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

                    • [^] # Re: Il dit qu'il est pas d'accord.

                      Posté par . Évalué à 2.

                      « Par ailleurs, chaque bateau/sous-marin emportait son propre bloc: ce n'est pas parce que tu obtiens celui d'un bateau que tu pourras décoder tous les messages de tous les autres bateaux. »

                      C'est toute l'histoire d'enigma et de la station X. Mais de ce que j'avais crus comprendre la station X a finalement était capable de déchiffrer un message sans en avoir la clef (et dans un temps raisonnable évidement).

                      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

                  • [^] # Re: Il dit qu'il est pas d'accord.

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

                    > on ne peut pas l'utiliser dans la vie de tous les jours (genre pour sécuriser
                    > une transaction bancaire).

                    On pourrait imaginer que quand tu ouvres un compte avec ta banque il te donne un disque avec 1To de données aléatoires. Quand tu tombes à court, tu retourne faire le plein.

                    C'est certainement moins pratique mais pas impossible.

                    pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

      • [^] # Re: Il dit qu'il est pas d'accord.

        Posté par . Évalué à 5.

        On peut très bien prouver P = NP sans pour autant trouver l’algorithme qui va bien, hein ;)
      • [^] # Re: Il dit qu'il est pas d'accord.

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

        Comme dit Moonz (et toi aussi, mais c'est du second degré, ça passe mal), le simple fait de prouver que P=NP ne changerait rien du tout. Car il resterait à trouver l'algo en P. Et il resterait à vérifier qu'il ne soit pas plus lent en début de courbe, pas exemple pour une clef de 16384 bits par exemple.

        Et le fait que P!=NP ne change rien du tout non plus puisque cela ne prouve pas que nos algo actuels ne peuvent pas être réduits. Ca prouve juste qu'il existe au moins un algo qui ne puisse pas.

        Donc N=NP ne change rien
        et N!=NP ne change rien non plus
        (dans les faits, pas dans la théorie bien entendu).
        • [^] # Re: Il dit qu'il est pas d'accord.

          Posté par . Évalué à 2.

          Et le fait que P!=NP ne change rien du tout non plus puisque cela ne prouve pas que nos algo actuels ne peuvent pas être réduits. Ca prouve juste qu'il existe au moins un algo qui ne puisse pas.
          Euh non... ça va bien plus loin: pour tous les problèmes NP-complets (et il y en a un paquet de connus), on saura alors qu'il sera impossible de trouver un algorithme polynomial déterministe.

          Cela dit, dans la pratique... ça ne prouve pas, par exemple, que l'ensemble des instances d'un problème générées, disons, pour rester dans le cas crypto, par un générateur de clés donné va donner une sous-classe de problèmes NP-complète.

          Donc bref, de toute façon, ça ne veut pas dire que le boulot s'arrête là !
        • [^] # Re: Il dit qu'il est pas d'accord.

          Posté par . Évalué à 3.

          Je pense que la plupart des chercheurs dans le domaines tentent de prouver P=NP en trouvant un algorithme. C'est généralement la méthode de démonstration la plus pratique et la plus simple.

          Il est bien plus compliquer de démontrer N!=NP car il faut montrer la "non-existance" d'un algorithme.

          Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

          • [^] # Re: Il dit qu'il est pas d'accord.

            Posté par . Évalué à 3.

            C'est un peu comme Dieu et les athées ;-) (oups, désolé ^^)
          • [^] # Re: Il dit qu'il est pas d'accord.

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

            a plupart des chercheurs dans le domaines tentent de prouver P=NP en trouvant un algorithme.
            Dans ce cas cela ne prouve rien. Car trouver UN algo n'indique pas que les ensembles sont égaux.
            Pour prouver par cette méthode, il faudrait trouver TOUS les algos. Pas gagné :-)

            Par contre ça fonctionne dans le cas où on souhaite prouver l'existence d'une propriété. Du genre "est-ce qu'il y a des armes de destructions massives en Iraq ?". Il suffit de trouver UNE arme pour prouver. A l'inverse, ne pas trouver d'arme ne prouve rien.
            • [^] # Re: Il dit qu'il est pas d'accord.

              Posté par . Évalué à 3.

              Tu n'y es pas. On prouve qu'un problème est NP complet en trouvant une transformation d'un problème dont on sait qu'il est NP-complet en notre problème, avec une transfo qui a de bonne propriétés, la transformation doit s'effectuer en temps polynomial.

              En gros ça implique que le problème est suffisamment complexe pour pouvoir exprimer un autre problème dont on connait la difficulté.

              Du coup si tu trouves un algorithme polynomial pour UN problème NP complet, tu trouves un algorithme polynomial pour ... tous les problèmes NP complet, en appliquant en préprocessing les transformations des preuves des problèmes en autre problème jusqu'à tomber sur celui pour lequel tu as un algo :)

              Comme les transformations sont polynomiales, l'agorithme résultant l'est aussi, CQFD. On sait aussi qu'il existe ce type de transformations pour tous les problèmes NP-complets entre eux.
              • [^] # Re: Il dit qu'il est pas d'accord.

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

                Je ne saisi pas.

                Par exemple factoriser un nombre est actuellement un problème NP. Si on arrive à factoriser un nombre en temps P, alors tous les problèmes NP pourrons être transformés en P ?
                • [^] # Re: Il dit qu'il est pas d'accord.

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

                  C'est une question d'isomorphisme. Ça te parle davantage ?
                  • [^] # Re: Il dit qu'il est pas d'accord.

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

                    A mon avis, l'un de nous deux a un niveau en maths "légèrement" plus élevé que l'autre :-)
                    Donc non, isomorphisme ne me dit rien du tout. Et puis ça n'entre pas dans une grille de Sudoku.

                    J'ai regardé l'article Wikipédia. Je pige en gros.
                • [^] # Re: Il dit qu'il est pas d'accord.

                  Posté par . Évalué à 2.

                  alors tous les problèmes NP pourrons être transformés en P ?
                  Oui.
                  • [^] # Re: Il dit qu'il est pas d'accord.

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

                    > > Par exemple factoriser un nombre est actuellement un problème NP. Si on arrive à factoriser un nombre en temps P, alors tous les problèmes NP pourrons être transformés en P ?
                    > Oui.

                    Euh, aux dernières nouvelles, la factorisation en facteurs premiers, c'est NP, mais pas NP-complet. Par exemple, ça se fait en temps polynomial sur un ordinateur quantique, alors qu'il n'y a toujours pas d'algo connus pour résoudre les problèmes NP-complets en temps polynomial sur ordinateurs quantiques (ou alors, j'ai raté un truc).

                    Résoudre un algo NP-complet en temps polynomial ferait tomber tous les autres, mais factoriser un nombre en facteurs premiers, non, ça ne suffirait pas.
                    • [^] # Re: Il dit qu'il est pas d'accord.

                      Posté par . Évalué à 2.

                      Intuitivement, ce n'est pas une preuve, le fait qu'on n'ait pas de réduction pour ces problèmes signifierait qu'ils dont moins dur que NP-complets : on arrive pas à exprimer SAT (NP complet) par exemple sous la forme de factorisation de nombre premiers ...

                      Donc à priori si on arrive à faire l'inverse, exprimer la factorisation sous la forme de SAT ou autre, on devrait prouver rigoureusement, si c'est pas déja fait, qu'ils sont plus faciles, et obtenir du même coup un algo polynomial, donc comme ça c'est pas très génant, en y réfléchissant un peu finalement.
                      • [^] # Re: Il dit qu'il est pas d'accord.

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

                        Je n'ai pas dit que j'avais la preuve que la factorisation était moins dure que NP-complet, j'ai dit que si on arrivait à factoriser en temps polynomial, ça ne suffirait pas à prouver que P=NP.
                • [^] # Re: Il dit qu'il est pas d'accord.

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

                  Le principe est simple :

                  En général pour prouver qu'un problème X est NP-complet, tu montres qu'il est équivalent à un autre problème Y qui est NP-complet à une transformation polynomiale près.

                  Donc si tu as un algo pour résoudre le problème Y en temps polynomial, il suffit d'appliquer une transformation polynomiale et tu peut résoudre le problème X.


                  Je vais faire une analogie foireuse mais qui j'espère permet de comprendre : Image que faire "a+b" soit NP-complet et que faire "-b" soit polynomial. Dans ce cas là, faire "a-b" est NP complet car avec une transformation polynomiale tu peut passer d'un problème à l'autre.

                  Donc si tu trouve un moyen de faire "a+b" est temps polynomial, tu sais aussi faire "a-b" en temps polynomial. (j'avais prévenu que l'analogie était foireuse...)


                  Le truc là dedans c'est justement que prouver qu'un problème est NP-complet par équivalence à un autre problème est beaucoup plus simple que faire la preuve depuis zero, donc quasiment toutes les preuves de NP-completude sont faites comme cela.

                  Et s'il existe des problèmes pour lesquels on à pas de réduction connues (à ma connaissance il n'y en as pas) la théorie nous dit que de toute façon elle existe, donc il suffit de ce mettre au boulot... Et vu l'expressivité de problèmes tel que le voyageur de commerce ou 3-SAT, il y a beaucoup de cas ou ce n'est pas si dur.
                  • [^] # Re: Il dit qu'il est pas d'accord.

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

                    Je viens de piger: c'est simplement la définition de "NP complet" qui exige que tous ces problèmes soient équivalents. C'est donc en fait un seul problème.

                    Je n'avais pas saisi que "NP" n'est pas la même chose que "NP complet".

                    Je reprends alors, vous corrigez si c'est idiot:
                    - résoudre n'importe quel problème NP-complet revient à résoudre tous les NP-complets (puisqu'en fait c'est la même chose)
                    - résoudre n'importe quel problème NP n'amène rien pour les autres (sauf découverte d'une grosse astuce)
                    • [^] # Re: Il dit qu'il est pas d'accord.

                      Posté par . Évalué à 3.

                      Je crois bien que c'est ça. Remarque que dire que tout les problèmes NP-chiants sont un seul problème c'est vue d'une manière très abstraite.

                      Voici une liste des problèmes :
                      http://fr.wikipedia.org/wiki/Liste_de_problèmes_NP-complets

                      Tu as des problèmes sur les graphes (voyageurs de commerces, plus grande clique,...), des problèmes algébrique (3-SAT,...), des problème de recherche opérationnelle (bin packing,...). C'est réellement très vaste.

                      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

                • [^] # Re: Il dit qu'il est pas d'accord.

                  Posté par . Évalué à 4.

                  En fait c'est un poil plus compliqué que ça, certains problèmes NP comme la factorisation en nombre premiers n'ont pas de telles transformations (lu dans le dernier numéro HS de pour la Science sur l'informatique quantique), ne sont pas forcément NP-complets et n'ont pas de réduction polynomiale vers un problème de NP ...

                  http://fr.wikipedia.org/wiki/D%C3%A9composition_en_produit_d(...)

                  Je sais pas si la preuve traîte de ce problème ou de ce type de problème, à voir :)
  • # Les journaux ne sont pas tout

    Posté par . Évalué à 8.

    > Il est d'ailleurs étonnant que l'article ait été proposé par email, et non soumis à un journal

    C'est peut-être plutôt une bonne chose de ne pas soumettre ça à un journal qui dépouille l'auteur de tous ses droits...

    Ne pas publier dans un de ces journaux n'enlève pas de valeur. Ils ne sont pas le seul moyen de valider ou invalider la preuve.
  • # D'autres

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

    Ce n'est pas la seule preuve proposée. Certaines de ces preuves ne sont toujours pas vérifiées : http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

    Je crois que l'ACM en a marre de recevoir tous les quatre matins des preuves sur la question et qu'ils ont limité le nombre d'envoi par an par auteur. La vérification de telles preuves est très coûteuse en temps et les preuves s'avèrent toujours fausses (jusqu'à maintenant).
  • # Facile

    Posté par . Évalué à 10.

    Il suffit de prouver que N != 1 et P != 0.

    Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

  • # Implication

    Posté par . Évalué à 4.

    Je pense qu'on peut prouver aisément que cette publication va venir perturber les vacances d'un grand nombre de chercheurs et enseignants en recherche op :)
    • [^] # Re: Implication

      Posté par . Évalué à 3.

      Heureusement, il y a assez peu de gens capables de comprendre la preuve et de vérifier si elle tient le coup, donc ça va peut-être perturber quelques centaines de gens, au mieux.

      Les autres attendront sûrement d'en savoir plus. Il y a des gens qui croient résoudre le problème tous les ans, et pour l'instant il tient le coup.
  • # Et pendent ce temps....

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

    D'autres chercheurs "démontrent" qu'il est toujours possible de finir un cube Rubick en moins de 20 coups.

    http://www.cube20.org/
    • [^] # Re: Et pendent ce temps....

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

      Voilà au moins quelque chose d'utile. Par exemple pour... heu... enfin ça peut servir à... hum... par exemple... Ouais bon, j'ai pas d'exemple qui me vient tout de suite, mais c'est utile ça au moins. Pas comme les trucs de math genre nombres premiers ou carré de l'hypothalamus.

      Le Rubik's c'est comme le vélo: une fois que tu as appris, c'est pour la vie. J'ai appris à le résoudre avec une méthode bête et méchante (une face, puis couronne centrale, puis le bas, sans optimisation. Wikipédia indique une moyenne de 110 mouvements, ça fait entre 1 et 2 minutes). J'étais ado. 25 ans plus tard je m'en souviens encore (j'ai résolu un Rubik's il y a 2 ans, sans jamais y avoir touché depuis mon adolescence).
      • [^] # Re: Et pendent ce temps....

        Posté par . Évalué à 2.

        On appelle ça la mémoire procédurale. Elle intervient notamment dans l'apprentissage d'une nouvelle habileté motrice comme le vélo.

        On dit aussi que c'est une mémoire implicite car on ne peut pas toujours décrire la procédure consciemment par la parole. Comme un mot de passe qui ne revient que quand on a un clavier sur lequel le taper.

        Wikipedia (en): http://en.wikipedia.org/wiki/Procedural_memory
        Une classification des différents types de mémoire (fr): http://reflexions.ulg.ac.be/cms/c_7610/la-memoire-multiple
        • [^] # Re: Et pendent ce temps....

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

          Comme un mot de passe qui ne revient que quand on a un clavier sur lequel le taper.
          ... et comme le code de carte bancaire qui ne fonctionne pas lorsque le clavier n'est pas dans le sens habituel :-) (Le UN peut être en bas ou en haut).
          • [^] # Re: Et pendent ce temps....

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

            Sur les nouveaux ATM de ma banque, le clavier est numérique, et l'ordre des chiffres change à chaque fois. Ça permet d'empêcher que quelqu'un retienne la position des doigts.
            (Bon, malheureusement, c'est juste une rotation, et peu-être un miroir, donc 8 positions, pas plus… Ça vaut pas l'espace de permutations complet.)
    • [^] # Re: Et pendent ce temps....

      Posté par . Évalué à 2.

      Le problème c'est que personnes n'a trouvé d'algorithme donnant la solution en 20 coups ça c'est une recherche vraiment intéressante parce que les problématiques en jeux doivent être transposables dans d'autres problèmes.

      Pour ceux qui est des joueurs de rubik's cube, le nombre de coups n'est pas nécessairement le plus important.

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

      • [^] # Re: Et pendent ce temps....

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

        >> Le problème c'est que personnes n'a trouvé d'algorithme donnant la solution en 20 coups

        Il n'existe pas forcément d'algorithme.
        C'est peut-être simplement une liste de cas tous différents…
        (Et puis, pour les solutions plus courtes, il faudrait remarquer qu'on est en cours de résolution d'un algo à 20 coups, et je sens qu'à peu-près 0 humain seraient capables de ça…)
        • [^] # Re: Et pendent ce temps....

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

          > Il n'existe pas forcément d'algorithme.
          > C'est peut-être simplement une liste de cas tous différents…

          Vu que l'espace d'état est fini, une liste de tous les cas, c'est un algorithme (bourrin, mais c'est un algorithme quand même).
    • [^] # Re: Et pendent ce temps....

      Posté par . Évalué à 0.

      et d'autres que c'est possible en chute libre:
      http://www.youtube.com/watch?v=b90GR3T-i7A

      If you can find a host for me that has a friendly parrot, I will be very very glad. If you can find someone who has a friendly parrot I can visit with, that will be nice too.

Suivre le flux des commentaires

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