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 Axioplase ıɥs∀ (site web personnel) . Évalué à 10.
http://arxiv.org/abs/1305.5976
[^] # Re: Lien
Posté par finss (site web personnel) . Évalué à 2.
Oups l'oubli de base.
Merci
\_o<
[^] # Re: Lien
Posté par psychoslave__ (site web personnel) . Évalué à 5.
Par quelle source tu es tombé sur ce papier ? À priori il était déjà sur le web dès 2009, et on en trouve des traces dans des publications dès 2007. Est-ce la publication sur arxive qui le met sous le feu des projecteurs ?
Sinon la semaine dernière c’est Yitang Zhang qui à fait parlé de lui en faisant un grand pas vers la résolution de la conjecture des nombres premiers jumeaux.
[^] # Re: Lien
Posté par Dr BG . Évalué à 6.
Il y a un mec qui maintient une page des différentes « preuves » : http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
[^] # Re: Lien
Posté par psychoslave__ (site web personnel) . Évalué à 2.
C’est de là que j’ai sortie les dates que j’ai cité. ;)
# Des commentaires de chercheur ?
Posté par Diagonale de Cantor (site web personnel) . É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 flan (site web personnel) . É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 Diagonale de Cantor (site web personnel) . É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 lenod . Évalué à 1.
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 Shuba . Évalué à 5.
J'ai entendu dire que ça pourrait résister quand même, pour plusieurs raisons:
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 baron . É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 Diagonale de Cantor (site web personnel) . É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 Kerro . Évalué à 1.
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 Diagonale de Cantor (site web personnel) . É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 Ays388 . É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 Ely . É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 oao . Évalué à 6.
Ton commentaire va très bien avec ton pseudonyme.
[^] # Re: Des commentaires de chercheur ?
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à 2.
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 ?
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Des commentaires de chercheur ?
Posté par Diagonale de Cantor (site web personnel) . Évalué à 3.
Non, puisque son argument était d'utiliser une surjection d'un ensemble A vers R pour montrer que A était indénombrable. Je suis en train de rechercher le papier :)
[^] # Re: Des commentaires de chercheur ?
Posté par kadalka . Évalué à -10.
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 Zylabon . É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
[^] # Re: Des commentaires de chercheur ?
Posté par Zylabon . Évalué à 3.
pardon, petite broutille, pour l'image de la ficelle avec le carrelage, ligne à ligne c'est débile, ça ne marche pas, parce que le coté du carrelage est infini lui aussi, on peut faire comme ça plutôt : en partant d'un coin et en parcourant le carrelage "de travers"
un peu comme pour l'ordre des données dans la compression jpeg
https://fr.wikipedia.org/wiki/Fichier:CompressionJPEGImage13.gif
Please do not feed the trolls
# Ma référence perso sur le sujet : pas de nouvelle
Posté par Thomas Douillard . Évalué à 6. Dernière modification le 30 mai 2013 à 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 Axioplase ıɥs∀ (site web personnel) . É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 flan (site web personnel) . É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 Zylabon . É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 Shuba . É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 à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.