P vs NP

[0100011]

Depuis deux semaines c'est l'effervescence autour d'une question centrale en informatique : la classe P est elle égale à la classe NP ? C'est un article de Deolalikar (un chercheur de HP) affirmant qu'il a prouvé que P différent de NP (ce que tout le monde pense) qui a mis le feu au poudre.

Il semblerait que sa solution soit fausse mais la stratégie utilisée (résumée ici) est nouvelle et semble intéressante par elle même. En ce qui me concerne j'ai toujours cru qu'on y arriverait par la logique et par un argument de type passage à la limite (en passant de SAT à la non décidabilité de la logique du premier ordre avec un argument de type "continuité" mais utilisé en marche arrière).

page wiki sur le papier : http://michaelnielsen.org/polymath1/index….r_P_vs_NP_paper

P vs NP fait parti des million dollars problems. On notera que pour l'instant le papier n'est plus accessible en ligne.

Article résumant "l'affaire" : http://topnews.com.sg/content/24386-expert…p-vs-np-problem

Researchers in the mathematics field are excited about the solution provided by an Indian Mathematician for the P vs NP problem, which is one of the major problems of mathematics. However, experts say that have found flaws and are uncertain if the solution will be accepted.

Vinay Deolalikar, who works at the Hewlett-Packard Labs (H P Labs) in California, claimed that he has successfully solved P vs NP problem and published the100-page proof online for evaluation and debate.

The P vs NP problem is one of the major problems in mathematics and one among the seven Clay Mathematics Institute Millennium Problems. The American think tank has announced a prize of 1 million dollars to the person whose solution to the problem is accepted.

If Deolalikar’s solution is accepted it will have implications on areas of computer applications, like security and machine intelligence. He has published a manuscript online but it is yet to be published in a known publication after which it might be accepted as the solution to the problem.

Manindra Agrawal, professor at the Indian Institute of Technology says that the proof lacks "specificity" and he was disappointed. He says now that Deolalikar is not even close. Agrawal and two of his graduate students became known when they solved an ancient Greek problem in 2002.

Deolalikar has taken notes of various analyses and says that he is now writing a new version of the proof taking in to account the technical concerns raised by some. The new drafts will not be released online and will be emailed to interested groups of researchers.

Neil Immerman of the University of Massachusetts says that he was able to spot a severe loophole in the solution. Immerman's says there is an error in attempting to describe the set of P in a particular way. Deolalikar has tried to show that there are problems with NP but not in P and thus P is not equal to NP. Immerman said that the method cannot be used because of the issue of other methods used in the solution.

The solution, if accepted has not, had a positive impact as it has already generated enough interest and enthusiasts across mathematics field are actively debating the issues relating to the problem.

[h16]

Intéressant, mais ça ne risque pas de susciter un grand débat ici. P est-il plus libéral que NP ?

[José]

Et il est mort à la fin ?

[h16]

En fait, ils survivent tous les deux. Mais après étude, ils sont demi-frères, même pas jumeaux et encore moins siamois.

[0100011]

Intéressant, mais ça ne risque pas de susciter un grand débat ici. P est-il plus libéral que NP ?

Si P=NP il faudra revoir les protocoles de e-commerce entre autre…

[Sloonz]

Si P=NP il faudra revoir les protocoles de e-commerce entre autre…

Non. Si P=NP, et qu’on trouve l’algo quivabien, et qu’il s’exécute dans un temps raisonnable (P ne veut pas dire rapide…)

[Invité jabial]

Non. Si P=NP, et qu’on trouve l’algo quivabien, et qu’il s’exécute dans un temps raisonnable (P ne veut pas dire rapide…)

+1

Enfin ceci dit si P=NP il faut commencer à les revoir quand même hein, pas attendre que ce soit cassé.

[Sloonz]

+1

Enfin ceci dit si P=NP il faut commencer à les revoir quand même hein, pas attendre que ce soit cassé.

Pourquoi donc ?

P ≠ NP n’interdit pas qu’il y ait de bonnes heuristiques permettant de faire « comme si ». Donc si on part par là, autant les revoir dès maintenant.

[Invité jabial]

Pourquoi donc ?

P ≠ NP n’interdit pas qu’il y ait de bonnes heuristiques permettant de faire « comme si ». Donc si on part par là, autant les revoir dès maintenant.

Tu ne peux pas faire comme si la différence n'existait pas. Ce n'est pas aussi binaire que ce que pensent les non-initiés, certes, mais ça resterait quand même une indication fondamentale qu'on peut trouver un algo, et ça lancerait nécessairement des équipes importantes sur cette piste, en faisant ainsi une prophétie auto-réalisatrice.

Ceci dit à la base je suis d'accord, on devrait passer tout de suite à la crypto quantique… si on peut.

[xavdr]

C'est bizare. Intuitivement je ne vois pas pourquoi P serait égal à NP. Trouver une solution et la vérifier sont 2 tâches complètement différentes. On peut vérifier facilement si un nombre résoud une équation paramétrique, mais si celle-ci provient d'une fonction suffisamment irrégulière, cela demande un temps arbitrairement grand pour en trouver une racine, ce qui peut représenter une charge exponentielle relativement à un paramètre contrôlant la finesse (l'irrégularité) de la fonction… De même si on cherche à restaurer des données codées dans un espace mémoire détérioré, on peut facilement vérifier la présence d'un magic number mais si le codage et sa déterioration l'imposent, on est obligé de passer la mémoire au crible pour le localiser, ce qui peut représenter une charge exponentielle si par exemple la grandeur de départ est la profondeur d'un arbre de données.

Ou alors je n'ai pas compris le problème posé ?

http://en.wikipedia.org/wiki/P_%3D_NP_problem

Ca fait longtemps que j'ai delaissé les problématiques de NP complétudes ^^

[Coldstar]

Ce serait bien si quelqu'un pouvait expliquer succinctement de quoi on parle.

[h16]

Ce serait bien si quelqu'un pouvait expliquer succinctement de quoi on parle.

Challenge.

[neuneu2k]

La crypto quantique : LOL

Les liens ou il est plus rentable de mettre un lien quantique que d'utiliser un lien classique et un one Time pad, je n'en ai jamais vu.

La crypto quantique, ce n'est pas de la crypto, ça ne manipule pas juste de l'information, c'est dépendent de la couche physique, et je n'ai pas confiance dans la couche physique :-)

Pour ma part, je pars du principe que p=np pour être dans le sens du risque et que si c'est contre la nsa que je dois me défendre, OTP point barre pour les données a rétention longue et la PKI, tout sauf RSA (si ils se sont paye un supercalculateur quantique ou avec un algo polynomial, c'est probablement pour RSA et pas ElGamal ou une courbe elliptique), et pour des données a faible valeur dans le temps.

[0100011]

Ce serait bien si quelqu'un pouvait expliquer succinctement de quoi on parle.

En informatique une manière de classer les problèmes est de mettre en liaison la taille des entrées avec le temps qu'il faut pour résoudre le problème. Ainsi pour trouver la plus grande personne parmi N personne tu dois faire N tests. Par contre si les gens sont en rangs déjà dans l'ordre de taille tu n'as plus de test à faire (tu prends le mec en bout de file).

Le problème NP standard est celui du voyageur de commerce : tu veux trouver le plus petit chemin qui passe une et une seule fois par une certaine liste de villes. En fait il n'y a rien d'essentiellement mieux que de faire toutes les combinaisons possibles (donc n * n-1 * n-2 * n-3 ….* 2 * 1) et de retenir la plus petite. Ca prend un temps fou meme avec l'ordinateur le plus puissant de la terre. Pire imaginons que tu ais un ordi qui mette 1 Min pour répondre au problème avec 60 villes, si tu ajoutes une ville de plus … il mettra 61 minutes, deux villes de plus 3600 minutes. Bref en changeant à peine les données de départ (62 villes plutôt que 60) tu te retrouves avec un truc impossible à traiter. Ce sont des problèmes "untractable" : on connait comment trouver la solution, pour cerrtaines instances on peut la calculer mais ça ne passe pas à l'échelle (explosion du temps de calcul).

La controverse P vs NP est la suivante : certains problèmes sont faciles à vérifier mais pas du tout à trouver. Par exemple la factorisation (qui n'est pas prouvé comme un problème NP complet en passant) si je te donne le chiffre suivant 125934404551 et que je te demande quels sont ses facteurs premiers tu es bien embêté (pas d'autre méthode encore une fois que d'essayer tous les nombres premiers et voir si la division tombe juste). Par contre si je te donne 196739 et 640109 c'est très facile de vérifier que c'est la bonne solution (une calculatrice suffit). Le problème est le suivant : est ce que tous les problèmes dont on peut vérifier la solution en temps P (le temps de calcul est un polynôme de la taille des entrées) sont solvables ou non en temps P ? (il existe un programme qui calcule la solution en temps polynômial) La question est de savoir si fondamentalement la vérification et la construction d'une solution pour une certaine classe de problèmes sont de même complexité.

Cette asymétrie est utilisée pour des protocoles cryptographiques dit "clef publique" : il s'agit d'une méthode qui permet de crypter les données par un moyen que tout le monde connait et une clef que tout le monde connait mais seul celui qui possède certaines infos secrètes peut retrouver l'information ainsi cryptée. C'est ce qui se passe (au moins au début) quand tu tapes https dans ton navigateur pour envoyer ton numéro de carte bleue ou consulter ton compte bancaire en ligne.

En gros si P=NP (ce que peu de gens soutiennent) alors il y a des chances que ce protocole ne tienne pas la route et soit "cassable".

[0100011]

Pour ma part, je pars du principe que p=np pour être dans le sens du risque et que si c'est contre la nsa que je dois me défendre, OTP point barre pour les données a rétention longue et la PKI, tout sauf RSA (si ils se sont paye un supercalculateur quantique ou avec un algo polynomial, c'est probablement pour RSA et pas ElGamal ou une courbe elliptique), et pour des données a faible valeur dans le temps.

OTP c'est très bien mais deux problèmes de fond subsistent :

1 - Engendrer aléatoirement la clef ce qui est un énorme problème pratique, cf pendant la seconde guerre mondiale on payait des secrétaire pour tirer des chiffres au hasard mais comme ça les faisait chier elles n'utilisaient plus les dés mais faisaient les séries 'à la main' et … ça se voyait. Une solution est … quantique (avec une source périodique on a du "vrai" hasard).

2- Tu ne résous pas le problème de communication sûre tu le déplaces. Si tu veux communiquer avec un OTP alors tu as communiqué la clef à ton correspondant. Qui te dit que lors de cette communication il n'y a pas eu fuite et si tu sais qu'il ne peut pas y avoir eu fuite pourquoi avoir besoin de protocole de cryptographie (il suffit d'envoyer le message directement de la manière que tu as utilisée pour la clef) ?

Sinon il y a des boites qui bossent déjà sur la crypto quantique : MagiQ, idQuantique, quintessence labs

[Librekom]

pendant la seconde guerre mondiale on payait des secrétaire pour tirer des chiffres au hasard mais comme ça les faisait chier elles n'utilisaient plus les dés mais faisaient les séries 'à la main' et … ça se voyait.

ne jamais faire confiance à sa secrétaire JAMAIS !

[Bastiat]

En fait, ils survivent tous les deux. Mais après étude, ils sont demi-frères, même pas jumeaux et encore moins siamois.

C'est sûr, de toute façon P ne peut être égal à Non P, ils sont bêtes ces matheux !

(Kassad, tu pourrais vulgariser un peu pour les néophyte, parce qu'une intro comme ça, ça fait mal au cul ?)

[henriparisien]

C'est sûr, de toute façon P ne peut être égal à Non P, ils sont bêtes ces matheux !

(Kassad, tu pourrais vulgariser un peu pour les néophyte, parce qu'une intro comme ça, ça fait mal au cul ?)

Ben, le résumé de kassad est très bien. Ce qui manque - peut-être - c'est un exemple de problème P.

Tu prends une liste de N nombre que tu veux trier par ordre croissant. L'une des solutions, c'est de se dire, je vais essayer toute les combinaisons possible. Et du coup le temps que tu vas y passer est de l'ordre de N ! (c'est à dire n * (n-1) * (n-2) etc..)

En utilisant cet algorithme, tu te retrouve avec le même problème que pour le voyageur de commerce de Kassad, tu rajoutes un nouvel élement, et le temps de calcul est multiplié par le nombre d'éléments.

Mais il existe d'autres algorithmes qui vont beaucoup plus vite pour ce calcul ; pour le tri de liste, l'ordre de grandeur classique c'est N * Log N ;

Pour le voyageur de commerce, on n'en connait aucun. Mais cela ne veut pas dire qu'il n'en existe pas. D'où la question P = NP ;

Et ces questions de dénombrabilité n'ont rien d'évident et d'intuitif. Il y a par exemple autant d'entier naturel que de nombre paire, alors qu'a l'évidence 1 est un entier naturel et n'est pas paire

Cela fait bien 20 ans que je mes connaissances n'ont pas été réactualisées sérieusement, mais sur la question annexe : la factorisation d'un nombre est-il un problème NP, j'aurais plutôt tendance à dire non, puisque ce problème particulier à une solution polynomiale avec un ordinateur quantique. Ce qui n'est pas le cas (à ma connaissance) du problème du voyageur de commerce.

[neuneu2k]

La crypto quantique, ce n'est pas de la crypto, ça ne manipule pas juste de l'information, c'est dépendent de la couche physique, et je n'ai pas confiance dans la couche physique :-)

Je vous l'avais bien dit

[Coldstar]

En informatique une manière de classer les problèmes est de mettre en liaison la taille des entrées avec le temps qu'il faut pour résoudre le problème.

Tu m'as perdu ici. Dommage pour le temps consacré à écrire le reste

[Randian shithead]

Cela fait bien 20 ans que je mes connaissances n'ont pas été réactualisées sérieusement, mais sur la question annexe : la factorisation d'un nombre est-il un problème NP, j'aurais plutôt tendance à dire non, puisque ce problème particulier à une solution polynomiale avec un ordinateur quantique. Ce qui n'est pas le cas (à ma connaissance) du problème du voyageur de commerce.

La factorisation d'entiers est un problème NP, mais à l'heure actuelle on ne sait pas s'il est NP-complet (avec de fortes raisons pour penser que non, entre autres celle que tu viens d'énoncer).Après le fait qu'on n'ait pas trouvé d'algo quantique ne prouve rien.

[0100011]

La factorisation d'entiers est un problème NP, mais à l'heure actuelle on ne sait pas s'il est NP-complet (avec de fortes raisons pour penser que non, entre autres celle que tu viens d'énoncer).Après le fait qu'on n'ait pas trouvé d'algo quantique ne prouve rien.

C'est surtout le fait que la factorisation est dans NP et co-NP et donc si la factorisation était un porblème NP-complet alors on aurait NP=co-NP ce qui n'est pas l'hypothèse la plus vraisemblable.