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
Journal P != NP : la preuve
9
août
2010
# Mais ké kidi?
Posté par Olorim . Évalué à 10.
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 JGO . Évalué à 9.
[^] # Re: Mais ké kidi?
Posté par Goffi (site web personnel, Mastodon) . Évalué à 10.
[^] # Re: Mais ké kidi?
Posté par Olorim . Évalué à 2.
Bon, ok, j'ai pas tout compris, mais au moins, maintenant, je comprend vaguement à quoi ça correspond...
[^] # Re: Mais ké kidi?
Posté par François Trahay (site web personnel) . Évalué à 9.
mea culpa.
[^] # Re: Mais ké kidi?
Posté par Olorim . Évalué à -1.
[^] # Re: Mais ké kidi?
Posté par tuXico . Évalué à -8.
[^] # Re: Mais ké kidi?
Posté par Olorim . Évalué à 2.
A part ça, tu as quelque chose à ajouter au débat?
[^] # Re: Mais ké kidi?
Posté par tuXico . Évalué à 1.
Il ne t'a absolument pas insulté.
Détends toi.
[^] # Re: Mais ké kidi?
Posté par Prae . Évalué à 7.
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 François Trahay (site web personnel) . Évalué à 10.
Désolé si ma réponse vous a choqué.
[^] # Re: Mais ké kidi?
Posté par tuXico . Évalué à 4.
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 Olorim . Évalué à -1.
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 Moonz . Évalué à -4.
[^] # Re: Mais ké kidi?
Posté par Obsidian . Évalué à 2.
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 tuXico . Évalué à 3.
[^] # Re: Mais ké kidi?
Posté par fearan . Évalué à 3.
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 briaeros007 . Évalué à 2.
[^] # Re: Mais ké kidi?
Posté par fearan . Évalué à 3.
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 Yusei (Mastodon) . Évalué à 2.
[^] # Re: Mais ké kidi?
Posté par Obsidian . Évalué à 2.
(Pataper, je sors tout seul. :-)
[^] # Re: Mais ké kidi?
Posté par 2PetitsVerres . Évalué à 4.
Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.
[^] # Re: Mais ké kidi?
Posté par briaeros007 . Évalué à 1.
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 Samuel (site web personnel) . Évalué à 8.
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 Moonz . Évalué à 9.
[^] # Re: Mais ké kidi?
Posté par François Trahay (site web personnel) . É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 Gof (site web personnel) . Évalué à 3.
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 Dup (site web personnel) . Évalué à 10.
[^] # Re: Mais ké kidi?
Posté par micha_mosk . Évalué à 6.
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 dinomasque . Évalué à 5.
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 20 ans !
[^] # Re: Mais ké kidi?
Posté par 2PetitsVerres . Évalué à 2.
-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 gaaaaaAab . Évalué à 2.
-return n
+return [1, n]
certes, 1 n'est pas premier, mais ils divise quand même n.
[^] # Re: Mais ké kidi?
Posté par micha_mosk . Évalué à 2.
Mais ça n’enlève rien au reste du commentaire.
[^] # Re: Mais ké kidi?
Posté par Dr BG . Évalué à 3.
[^] # Re: Mais ké kidi?
Posté par moi1392 . Évalué à 4.
À 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 Maclag . Évalué à 9.
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 fearan . Évalué à 2.
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 Oscar Blumberg . Évalué à 4.
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 barmic . Évalué à 3.
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 Axioplase ıɥs∀ (site web personnel) . Évalué à 5.
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 François Trahay (site web personnel) . Évalué à 3.
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 Matthieu Moy (site web personnel) . Évalué à 3.
On considère en théorie que « polynomial = pas cher » et « exponentiel = cher », mais un algo en N^100, en pratique, c'est pas si différent d'un truc exponentiel (le comportement pour N très grand est différent, mais de toutes façons, on aura atteint les limites de la machine bien avant de s'en rendre compte).
[^] # Re: Il dit qu'il est pas d'accord.
Posté par riba . Évalué à 2.
Tout ces spécialistes sont des hommes?
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Gof (site web personnel) . Évalué à 2.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par riba . Évalué à 2.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par darkhi . Évalué à 3.
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 fearan . Évalué à 2.
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 pasBill pasGates . Évalué à 4.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par darkhi . Évalué à 1.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Krunch (site web personnel) . Évalué à 6.
C'est déjà le cas de tous les cryptosystèmes asymétriques si je ne m'abuse.
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par darkhi . Évalué à 1.
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 briaeros007 . Évalué à 5.
Tout comme AES ou autres... C'est un algo symétrique.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par François Trahay (site web personnel) . Évalué à 1.
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 beagf (site web personnel) . Évalué à 3.
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 François Trahay (site web personnel) . Évalué à 2.
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 Duncan Idaho . Évalué à 2.
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 François Trahay (site web personnel) . Évalué à 3.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par briaeros007 . Évalué à 3.
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 2PetitsVerres . Évalué à 3.
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 barmic . Évalué à 2.
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 Krunch (site web personnel) . Évalué à 2.
> 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 François Trahay (site web personnel) . Évalué à 2.
C'est moins efficace que le coup du disque dur, mais c'est quand même vachement plus pratique que de devoir se promener avec un disque dur :)
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Krunch (site web personnel) . Évalué à 2.
Pour l'utilisateur ça ressemble peut-être mais dans le principe c'est quand même assez différent du masque jetable : http://fr.wikipedia.org/wiki/Masque_jetable
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Moonz . Évalué à 5.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Kerro . É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.
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 Aldoo . Évalué à 2.
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 barmic . Évalué à 3.
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 Aldoo . Évalué à 3.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Kerro . Évalué à 5.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Kerro . Évalué à 1.
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 Thomas Douillard . Évalué à 3.
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 Kerro . Évalué à 2.
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 feth . Évalué à 4.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Kerro . Évalué à 3.
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 feth . Évalué à 5.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par briaeros007 . Évalué à 2.
Oui.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Matthieu Moy (site web personnel) . Évalué à 3.
> 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 Thomas Douillard . Évalué à 2.
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 Matthieu Moy (site web personnel) . Évalué à 2.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par beagf (site web personnel) . Évalué à 4.
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 Kerro . Évalué à 3.
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 barmic . Évalué à 3.
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 Thomas Douillard . Évalué à 4.
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 :)
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Thomas Douillard . Évalué à 2.
# Les journaux ne sont pas tout
Posté par mickabouille . Évalué à 8.
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.
[^] # Re: Les journaux ne sont pas tout
Posté par lolop (site web personnel) . Évalué à 6.
Il me semble que le mathématicien russe isolé, qui a résolu récemment un des autres problèmes à 1M$, est aussi passé par le web et non par les organes de publication habituellement reconnus.
Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN
[^] # Re: Les journaux ne sont pas tout
Posté par François Trahay (site web personnel) . Évalué à 2.
La, le chercheur n'est pas un académique, il bosse chez HP.
[^] # Re: Les journaux ne sont pas tout
Posté par Hank Lords . Évalué à 7.
et il n'est pas passé par le cursus traditionnel de publication dans une grande revue scientifique, mais il a publié sa démonstration sur le site de publication http://arxiv.org/
[^] # Re: Les journaux ne sont pas tout
Posté par gaaaaaAab . Évalué à 6.
The preliminary version made it to the web without my knowledge.
Il l'a envoyé à ses pairs pour relecture, pas pour diffusion publique.
# D'autres
Posté par Dr BG . Évalué à 8.
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).
[^] # Re: D'autres
Posté par Thierry Thomas (site web personnel, Mastodon) . Évalué à 4.
# Facile
Posté par 2PetitsVerres . Évalué à 10.
Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.
[^] # Re: Facile
Posté par kowalsky . Évalué à -3.
# Implication
Posté par fcartegnie . Évalué à 4.
[^] # Re: Implication
Posté par Yusei (Mastodon) . Évalué à 3.
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 Gof (site web personnel) . Évalué à 7.
http://www.cube20.org/
[^] # Re: Et pendent ce temps....
Posté par Kerro . Évalué à 2.
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 j_m . Évalué à 2.
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 Kerro . Évalué à 3.
... 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 Axioplase ıɥs∀ (site web personnel) . Évalué à 2.
(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 barmic . Évalué à 2.
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 Axioplase ıɥs∀ (site web personnel) . Évalué à 2.
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 Matthieu Moy (site web personnel) . Évalué à 3.
> 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 pasScott pasForstall . Évalué à 0.
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 à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.