P = NP
P <> NP
Pour information : cet article est très contesté sur un point facile à mettre en évidence, à savoir que les bulles de savon se stabilisent (et pas de façon instantanée (et donc il faut prendre ce temps en considération)) dans une position qui est un minimum local, mais pas forcément un minimum global (pour n > 3), donc, "elles" ne résolvent pas le problème de Steiner.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Ok, javais rien compris (mais franchement ...).Envoyé par photon57
Cependant, l'article reste interessant mais ce que javais dit reste, je m'attends à plus d'assise expérimentale car comme je l'ai dit et Médiat confirme, ça peut marcher très bien pour certaines valeurs de n faible et puis plus rien ensuite.
Personnellement, je pense qu'on a plus de chances de trouver des exemples en génétique ou en biologie qu'avec des bulles de savons, pour les raisons que j'ai cité.
Hello,
oui en effet, Aaronson (entre autre) a bien décortiqué le problème en allant jusqu'à tester dispositif pour quelques petites valeurs de n (ce qui lui a d'ailleurs permi de gagner un pari). Rien ne garanti que le minimum global est atteint, donc «la nature» ne fait mieux que nos algorithmes, i.e. si on obtient toujours un résultat en temps polynomial alors il ne s'agit que d'une heuristique qui approxime la meilleure solution.
L'argument du minimum local doit être applicable à de nombreux processus physiques, donc à priori il n'y aurait aucun manière d'accélerer exponentiellement la résolution d'un problème NP complet ?
Par exemple, si n va de 1 à 200 à priori, on peut par exemple :
- penser que le processus physique n'est pas modélisable à l'heure actuelle avec nos mathématiques
- poser que la résolution naturelle met en oeuvre différents types de stratégies mathématiques résolutions suivant les différentes valeurs de n
- poser que la résolution naturelle met en oeuvre une méthode générale valable de 1 à 200, ce qui constitue déjà, surement un exploit
- que P = NP
- ... (?)
Il faut aussi noter qu'en physique, contrairement aux mathématiques, on peut surement imaginer que pour tous les problèmes une valeur de n pour lequel le phénomène ne se produit plus (après une certaines valeur de n, on "change" de problème : toutes les théories physiques étant valable seulement dans un domaine de validité).
Il faut aussi noter, qu'il est difficile de s'assurer que la résolution naturelle en est effectivement, car (pour n suffisament grand) nous ne pouvons justement pas connaitre en un temps raisonnable la solution. On ne peut que dire qu'on n'arrive pas à faire mieux, et postuler comme une conjecture, qu'il s'agit effectivement bien d'une résolution naturelle.
Dernière modification par invite7863222222222 ; 15/02/2012 à 13h37.
Ce qui est déjà pas mal.
