0100011 Posté 20 avril 2007 Signaler Posté 20 avril 2007 La compagnie Net Flix propose une voie de financement de sa R&D pour le moins originale : le concours. Ils proposent un million de dollars à qui pourra leur fournir une idée (pas forcément un logiciel complet) permettant d'améliorer leurs prévisions sur l'estimation que font leurs clients des films. Avis aux amateurs : http://www.netflixprize.com/index En fait il s'agit d'une version commerciale des millenium problems de math de l'institut Clay : http://www.claymath.org/millennium/ Dernièrement G. Perelman (http://en.wikipedia.org/wiki/Grigori_Perelman) qui a résolu la conjecture de Poincarré pourrait réclamer son million, mais en savant fou qui se respecte il refuse de le faire… Bon, sur ce, je retourne plancher sur P=NP, qui sait ça pourrait me rendre riche
Libéralissime Posté 20 avril 2007 Signaler Posté 20 avril 2007 Cette approche n'est nouvelle que dans un pays où la recherche est en voie de soviétisation totale !
A.B. Posté 20 avril 2007 Signaler Posté 20 avril 2007 Tient ils ont fait des progres, le meilleur est a 7% d'amélioration… je m'y suis essayé mais j'ai arrêté faute de temps, si vous voulez des idées, ce domaine c'est un peu mon dada. Dans le meme genre il y a les x-prize qui ont eu du succès. J'ai vu dernièrement une conférence de Tabarrok précisément sur ce sujet, les "bounties". L'idée était qu'un bounty est efficace quand on connaît précisément le résultat souhaité mais pas la manière d'y parvenir.
0100011 Posté 20 avril 2007 Auteur Signaler Posté 20 avril 2007 En fait Perelman a mis une dizaine d'années, à ce qu'il semblerait, pour résoudre la conjecture de Poincarré. Finalement 100 000 $ par an c'est vraiment pas cher pour se payer un pur génie.
WALDGANGER Posté 22 décembre 2008 Signaler Posté 22 décembre 2008 un petit up… Par hasard, j'ai découvert hier la question P vs NP. Je pense avoir à peu près compris l'idée mais un point me fait douter. Pour illustrer les problèmes de type NP, je vois que le problème du " voyageur de commerce" revient souvent. J'ai cru comprendre qu'un problème de type NP ne pouvait pas être résolu en temps polynomial mais que l'on pouvait vérifier sa solution en temps polynomial. Je comprends bien cette différence sur d'autres exemples (comme une factorisation), mais pour le voyageur de commerce je ne vois pas la différence de complexité entre la résolution du problème et la vérification de la solution, les deux nécessitent de calculer toutes les routes non? Autre question, j'ai cru lire également que si l'on arrivait à ramener le problème du voyageur de commerce à un problème de type P alors cela montrerait que tous les problèmes de type NP peuvent se ramener à des problèmes de type P. C'est bien le cas?
h16 Posté 23 décembre 2008 Signaler Posté 23 décembre 2008 Autre question, j'ai cru lire également que si l'on arrivait à ramener le problème du voyageur de commerce à un problème de type P alors cela montrerait que tous les problèmes de type NP peuvent se ramener à des problèmes de type P. C'est bien le cas? Oui.
Emi Posté 13 janvier 2009 Signaler Posté 13 janvier 2009 Autre question, j'ai cru lire également que si l'on arrivait à ramener le problème du voyageur de commerce à un problème de type P alors cela montrerait que tous les problèmes de type NP peuvent se ramener à des problèmes de type P. C'est bien le cas? Oui. Car le voyageur de commerce est un problème NP-Complet, c'est à dire que résoudre n'importe quel problème dans NP peut se ramener à résoudre le voyageur de commerce. C'est le théorème de cook qui exhibe le premier problème NP-Complet, SAT
0100011 Posté 13 janvier 2009 Auteur Signaler Posté 13 janvier 2009 un petit up…Par hasard, j'ai découvert hier la question P vs NP. Je pense avoir à peu près compris l'idée mais un point me fait douter. Pour illustrer les problèmes de type NP, je vois que le problème du " voyageur de commerce" revient souvent. J'ai cru comprendre qu'un problème de type NP ne pouvait pas être résolu en temps polynomial mais que l'on pouvait vérifier sa solution en temps polynomial. Je comprends bien cette différence sur d'autres exemples (comme une factorisation), mais pour le voyageur de commerce je ne vois pas la différence de complexité entre la résolution du problème et la vérification de la solution, les deux nécessitent de calculer toutes les routes non? J'avais laissé passé ce fil… Deux remarques. 1 Techniquement P vs NP se pose sur des probèmes dits de décisions, c'est à dire que le programme te sort oui ou non et rien d'autre. En l'occurrence pour le voyageur de commerce la question précise est "existe t'il un circuit dont la taille est inférieure à k". La vérification est débilissime : si quelqu'un vient avec un circuit et te dit qu'il fait moins de k alors tu as juste à regarder sur la carte qu'il ne t'embobine pas. Si tu veux le calcul du circuit le plus le court alors là le problème est NP-hard ce qui n'est pas la même chose que NP (en fait on ne sait pas exactement, c'est justement une des questions à 1 000 000 $). Maintenant pour vérifier que le circuit qu'on te donne est le plus court c'est facile : tu prends sa taille L et tu appliques la version "décision" du voyageur de commerce, si on te répond qu'il n'y a pas de chemin plus petit que L alors gagné . 2. Quant au problème de la factorisation on ne sait pas s'il est NP-complet, mais il est NP.
Messages recommandés
Archivé
Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.