0100011 Posted April 20, 2007 Report Posted April 20, 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 Posted April 20, 2007 Report Posted April 20, 2007 Cette approche n'est nouvelle que dans un pays où la recherche est en voie de soviétisation totale !
A.B. Posted April 20, 2007 Report Posted April 20, 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 Posted April 20, 2007 Author Report Posted April 20, 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 Posted December 22, 2008 Report Posted December 22, 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 Posted December 23, 2008 Report Posted December 23, 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 Posted January 13, 2009 Report Posted January 13, 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 Posted January 13, 2009 Author Report Posted January 13, 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.
Recommended Posts
Archived
This topic is now archived and is closed to further replies.