Problème NP complets résolus dans la nature ?

[invite7863222222222]

Bonjour,

j'aimerai savoir s'il y a des problèmes dans la nature en biologie ou en génétique par exemple qui sont NP-complets et qui semblent être résolus "naturellement" comme s'ils étaient des problèmes P (en temps polynomial).

C'est plus difficile à mettre en évidence qu'on peut croire, car à k fixé on peut réussir à trouver des résolutions en temps polynomial, si k n'est pas trop élevé par rapport au temps passé à essayer de "analyser" le problème en tant que cas particulier (voir http://fr.wikipedia.org/wiki/Problèm...es_polynomiaux).

L'idée est que la recherche de cas NP-complets "résolus" par la nature pourrait aider à résoudre (si la nature réussit à résoudre un NP-complet comme un P) ou à nous donner des pistes pour penser que P<>NP, si on ne réussit apparemment pas trop à trouver de telles résolutions dans la nature.

J'en ai aussi profité pour mettre un sondage sur la question (P = NP ou P<>NP ?).

PS : je poste la discussion ici car la question du problème P=NP ou P<>NP est un peu relié avec aux sciences de la nature ce qui donc peut aussi poser des questions d'ordre épistémologique.
-----

[invite7863222222222]

En fait, désolé pour les fautes d'orthographes.

[invite7863222222222]

Décidément, je cumule.

[invitebdf515f4]

Mon petit doigt me dit que si ca existait, ça répondrait directement à la question. On pourrait directement répondre P=NP.

Ensuite, il faut bien comprendre qu'un problème NP-complet est facile à résoudre. Par exemple, le problème du voyageur de commerce. Je le résoud facilement de tête avec 3 villes. Le soucis est bien de trouver une technique de résolution dont le temps augmente polynomialement lorsque la taille du problème augmente. Trouver un système naturel qui le résoud rapidement pour une valeur particulière du nombre de villes, ça me semble envisageable. Trouver un système naturel qui permet de le résoudre en temps polynomial par rapport au nombre de villes, ça s'apparente à la quête du graal, à mon humble avis.

[A voir en vidéo sur Futura]

[invite7863222222222]

Ensuite, il faut bien comprendre qu'un problème NP-complet est facile à résoudre

Rassurez-vous, je l'ai parfaitement compris. D'ailleurs, je ne vois pas l'intérêt de cette remarque étant donné, que je l'ai déjà bien précisé en citant le théorème de Robertson-Seymour.

Trouver un système naturel qui permet de le résoudre en temps polynomial par rapport au nombre de villes, ça s'apparente à la quête du graal, à mon humble avis

Il y a plus d'avis semble-t-il dans ce sens, mais il existe aussi des avis contraires, et rien n'est encore démontré.

Personnellement, moi, je me dis que c'est possible que P = NP, seul le coté "extraordinaire" des conséquences tendent parfois à me laisser penser que ce n'est pas le cas (mais je considère quand même que cet un argument dans son expression actuelle dans mon esprit, n'a pas de valeur suffisante pour me convaincre du contraire que P = NP).

[Matmat]

Ceux qui ne pensent ni P=NP ni P<>NP répondent quoi au sondage ?

[invite4492c379]

Ils ne répondent pas ???
Personnellement j'aime à penser que FPT=W[1]

[invite7863222222222]

Ceux qui ne pensent ni P=NP ni P<>NP répondent quoi au sondage ?

Je ne sais pas. Mais, j'attends clairement plus des réponses à la question (exemples de tels problèmes dans la nature, dont on pourrait être intéressé par la manière où il pourrait sembler être résolu") que j'ai posé dans mon premier message qu'au sondage.

[invite4492c379]

Je ne sais pas. Mais, j'attends clairement plus des réponses à la question (exemples de tels problèmes dans la nature, dont on pourrait être intéressé par la manière où il pourrait sembler être résolu") que j'ai posé dans mon premier message qu'au sondage.

La question est complexe. Elle suppose que l'on peut identifier dans «la nature» des phénomènes que l'on peut modéliser de manière à les réduire à un problème NP-complet (qui implicitement ne font donc pas partie de «la nature»).
Néanmoins, je pense qu'un article comme http://arxiv.org/pdf/cs/0406056.pdf devrait certainement t'intéresser.

Un article qui a fait des bulles

[invite7863222222222]

Elle suppose que l'on peut identifier dans «la nature» des phénomènes que l'on peut modéliser de manière à les réduire à un problème NP-complet (qui implicitement ne font donc pas partie de «la nature»).

Pour être plus concret, des phénomènes qui ressemblent par exemple à celui du problème du voyageur.

La question demande donc qu'on puisse effectivement trouver des phénomènes où la question est apparue se poser sous la forme d'un problème, donc d'une optimisation nécessaire.

La motivation est dans la contrainte de fitness par rapport à l'environnement voulue par l'évolution, et la richesse des phénomènes de la nature.

[invite4492c379]

Pour être plus concret, des phénomènes qui ressemblent par exemple à celui du problème du voyageur.

La question demande donc qu'on puisse effectivement trouver des phénomènes où la question est apparue se poser sous la forme d'un problème, donc d'une optimisation nécessaire.

La motivation est dans la contrainte de fitness par rapport à l'environnement voulue par l'évolution, et la richesse des phénomènes de la nature.

L'article propose de considérer STP (steiner tree problem) qui est un problème NP-complet si l'espace est discret. Les données sont simples, tu disposes n points sur un plan, il faut trouver un graphe tel que les n points sont des sommets de ce graphe et la somme totale des longueur des arêtes est minimale. Mathématiquement le problème est NP-complet, physiquement le problème est résolu en temps polynomial par rapport au nombre de points très simplement : tu prends deux plaques espacées (mais pas trop) attachées par des goupilles qui représentent les n points ; tu trempes le dispositif dans l'eau savonneuse, les bulles vont délimiter un tel graphe.
Donc en gros si on est d'accord avec les points suivant :
1. STP (sous certaines conditions) est NP complet
2. des bulles de savon construisent un arbre de Steiner en temps polynomial
3. les bulles de savon sont des objets de physique classique
4. la physique classique peut être simulée (en temps polynomial) par une machine de Turing
Alors P=NP.

[invitebdba5ac3]

La motivation est dans la contrainte de fitness par rapport à l'environnement voulue par l'évolution, et la richesse des phénomènes de la nature.

voulue par l’évolution ? ........... tu es vitaliste ?

[invite7863222222222]

L'article propose de considérer STP (steiner tree problem) qui est un problème NP-complet si l'espace est discret. Les données sont simples, tu disposes n points sur un plan, il faut trouver un graphe tel que les n points sont des sommets de ce graphe et la somme totale des longueur des arêtes est minimale. Mathématiquement le problème est NP-complet, physiquement le problème est résolu en temps polynomial par rapport au nombre de points très simplement : tu prends deux plaques espacées (mais pas trop) attachées par des goupilles qui représentent les n points ; tu trempes le dispositif dans l'eau savonneuse, les bulles vont délimiter un tel graphe.
Donc en gros si on est d'accord avec les points suivant :
1. STP (sous certaines conditions) est NP complet
2. des bulles de savon construisent un arbre de Steiner en temps polynomial
3. les bulles de savon sont des objets de physique classique
4. la physique classique peut être simulée (en temps polynomial) par une machine de Turing
Alors P=NP.

Là tu considères le terme "résolution en temps polynomiale", par rapport à une échelle de temps et non par rapport à la taille du problème.

Ce n'est pas le temps mis à taille fixée par rapport à une échelle de temps en disant par exemple, que pour 4 points, et une échelle delta 2 ms , le problème a été résolu en 10 secondes, dont donc 10s = 5 x 2s = 5 delta donc c'est polynomial donc c'est un problème NP.

P = NP ou P <> NP s'exprime en constatant le temps mis en faisant varier la taille du problème et en relevant le temps jusqu'à trouver la solution.

Si ce temps tend exponentiellement avec la taille du problème, on va vite devoir attendre très très longtemps dès que la taille du problème va augmenter.

Une unique expérience avec n fixé, n'apporte rien à la question.

[invite7863222222222]

voulue par l’évolution ? ........... tu es vitaliste ?

Non pas du tout (je vais être plus prudent, ne sachant pas trop ce qu'est le vitalisme : en tout cas pas pour cette raison) : par exemple, si on avait un exemple que P = NP suivant ces considérations, j'en déduirais aucune conclusion vitaliste, juste que ce qu'on peut trouver dans la nature dépasse apparemment notre imagination. Dans le cas contraire, j'en déduirais simplement que mon idée était pas bonne.

[invite4492c379]

Là tu considères le terme "résolution en temps polynomiale", par rapport à une échelle de temps et non par rapport à la taille du problème.

Ce n'est pas le temps mis à taille fixée par rapport à une échelle de temps en disant par exemple, que pour 4 points, et une échelle delta 2 ms , le problème a été résolu en 10 secondes, dont donc 10s = 5 x 2s = 5 delta donc c'est polynomial donc c'est un problème NP.

P = NP ou P <> NP s'exprime en constatant le temps mis en faisant varier la taille du problème et en relevant le temps jusqu'à trouver la solution.

Si ce temps tend exponentiellement avec la taille du problème, on va vite devoir attendre très très longtemps dès que la taille du problème va augmenter.

Une unique expérience avec n fixé, n'apporte rien à la question.

Pour paraphraser les auteurs de l'article :

Building the structure and the solution (and the container for the solution) requires steps linear in the size of n, and dipping and withdrawing make two steps, so despite the fact that STP is NP-complete, the physical process just described — let’s call it As — is apparently carried out well within O(n^k), for some constant k.

Je ne fixe pas n, tes propos ne sont pas très clairs.

[invite7863222222222]

Pour paraphraser les auteurs de l'article :


Je ne fixe pas n, tes propos ne sont pas très clairs.

Tu n'as pas fait varier n non plus, j'ai répondu par rapport seulement à ce que tu avais écrit comme tu me l'as demandé.

Pour ces raisons, je trouve que tes propos ne sont pas clairs.

C'est peut-être juste une petite incompréhension : si suivant l'article, ça varie polynomialement par rapport à la taille, tu en conclues que P = NP ?

Pour info, c'est aussi ce que je concluerais.

Ceci dit, je dois avouer que le fait que ce soit anglais aide pas à ma démarche critique par rapport à cet article.

[inviteccac9361]

Bonjour,

2. des bulles de savon construisent un arbre de Steiner en temps polynomial

D'accord, mais il s'agit ici d'un traitement en parallele produit par la nature.
Ce n'est pas calculable de manière classique.

Qui plus est, je ne suis pas sùr que cette méthode des bulles fonctionne à tous les coups.

[invite4492c379]

Tu n'as pas fait varier n non plus, j'ai répondu par rapport seulement à ce que tu avais écrit comme tu me l'as demandé.

Pour ces raisons, je trouve que tes propos ne sont pas clairs.

Je parle de STP (qui est dans la liste originelle de Karp) ... donc, si on lit l'article, on comprend vite que n n'est pas fixé.

[invite7863222222222]

Je parle de STP (qui est dans la liste originelle de Karp) ... donc, si on lit l'article, on comprend vite que n n'est pas fixé.

Ok, je répète alors ce que j'ai édité plus haut (au cas où tu ne l'aurais pas lu) :

C'est peut-être juste une petite incompréhension : si suivant l'article, ça varie polynomialement par rapport à la taille, tu en conclues que P = NP ?

Pour info, c'est aussi ce que je concluerais.

Ceci dit, je dois avouer que le fait que ce soit anglais aide pas à ma démarche critique par rapport à cet article.

[invite4492c379]

Bonjour,
D'accord, mais il s'agit ici d'un traitement en parallele produit par la nature.
Ce n'est pas calculable de manière classique.
Qui plus est, je ne suis pas sùr que cette méthode des bulles fonctionne à tous les coups.

Hello,

donc tu réfutes en fait la partie «4. la physique classique peut être simulée (en temps polynomial) par une machine de Turing». Oui, ça se tient je suppose.
Maitenant le côté parallèle produit par la nature je doute, je rappelle qu'à tout algorithme parallèle correspond un algorithme séquentiel équivalent (la réduction du premier au second étant polynomiale).

[invite7863222222222]

Hello,

donc tu réfutes en fait la partie «4. la physique classique peut être simulée (en temps polynomial) par une machine de Turing». Oui, ça se tient je suppose.
Maitenant le côté parallèle produit par la nature je doute, je rappelle qu'à tout algorithme parallèle correspond un algorithme séquentiel équivalent (la réduction du premier au second étant polynomiale).

Attention, ça peut être localement polynomial, mais peut-être pas pour tout n, je n'ai pas lu l'article mais ils sont aller jusqu'à n = combien ?

Je vais essayer de lire cet article.

[invite4492c379]

Ok, je répète alors ce que j'ai édité plus haut (au cas où tu ne l'aurais pas lu) :

C'est peut-être juste une petite incompréhension : si suivant l'article, ça varie polynomialement par rapport à la taille, tu en conclues que P = NP ?

Pour info, c'est aussi ce que je concluerais.

Ceci dit, je dois avouer que le fait que ce soit anglais aide pas à ma démarche critique par rapport à cet article.

Personnellement j'en dis pas grand chose sinon que leur démarche est originale ... Tout ce qu'ils disent en fait pour cette partie est que puisque STP est NP complet, que le problème est résolu en temps polynomial par «la nature» en utilisant des objets de la physique classique, alors si la physique classique peut être simulée en temps polynomial par une machine de Turing alors il existe donc un algorithme de P qui résout STP et du coup P=NP.
Cela ne signifie pas forcément qu'un tel algorithme soit utilisable pour autant qu'il existe.

[invite4492c379]

Attention, ça peut être localement polynomial, mais peut-être pas pour tout n, je n'ai pas lu l'article mais ils sont aller jusqu'à n = combien ?

Je vais essayer de lire cet article.

On va faire ça.

[invite7863222222222]

4. la physique classique peut être simulée (en temps polynomial) par une machine de Turing»

Pour moi, plus exactement, on postulerait : "tous les phénomènes physiques se modélisant comme un problème NP-complets peuvent être simulés (en temps polynomial) par une machine de Turing, si on observe une résolution en temps polynomial 'naturelle' ". Ce qui n'est effectivement pas évident.

[invite4492c379]

Pour moi, plus exactement, on postulerait : "tous les phénomènes physiques se modélisant comme un problème NP-complets peuvent être simulés (en temps polynomial) par une machine de Turing, si on observe une résolution en temps polynomial 'naturelle' ". Ce qui n'est effectivement pas évident.

Toujours en paraphrasant les auteurs :

Our argument shows that if P=/=NP, digital physics is incorrect. Since it must be true that all physical phenomena can in principle be modeled in information-processing terms of some kind, P=/=NP thus immediately implies, courtesy of our arguments, that hypercomputational processes exist in the physical universe.
If you believe, as many do, that hypercomputational processes are always merely mathematical, and never physically real, you can’t be rational and at the same time refuse to accept our case for P=NP.

où =/= signifie «non égal».
Cette conclusion est intéressante.

[inviteccac9361]

donc tu réfutes en fait la partie «4. la physique classique peut être simulée (en temps polynomial) par une machine de Turing». Oui, ça se tient je suppose.
Maitenant le côté parallèle produit par la nature je doute, je rappelle qu'à tout algorithme parallèle correspond un algorithme séquentiel équivalent (la réduction du premier au second étant polynomiale).

Oui, les lois physiques s'écoulent en parallèle.

Enfin, avec un petit biais conceptuel.
Le cas des jumeaux en relativité restreinte propose par exemple un fonctionnement qui ne l'est plus tout à fait.
En "parallèle" suppose un temps commun, or ceci n'est vrai qu'en première approximation.
Mais ça ne change rien au problème je pense, puisque l'information ne peut être transmise qu'à une vitesse limite.

[invite7863222222222]

Mais ça ne change rien au problème je pense, puisque l'information ne peut être transmise qu'à une vitesse limite.

Oui je pense qu'on résout bien numériquement des problèmes relativistes.

Sinon, j'ai parcouru le document, les conclusions possibles me semblent vraiment riches. Entre hypothèse de physique digitale comme il en parle dans le papier/non réductibilité de la physique à un problème mathématique/existences pleins de problèmes physiques pourtant simples alors qu'on pourrait n'être qu'intéressé à trouver de nouvelles théories comme si tout le reste était trop simple (j'ai aussi un en tête un exemple de physique/chimie/géométrie sur la différence de densité de l'eau à l'état liquide et solide que nous ne savons pas calculé) etc. ça donne à réfléchir...

J'ai néanmoins une petite critique et réserve à faire à l'article par rapport à ceci :

is apparently carried out well within , for some constant k.


C'est dommage et ça gâche un peu tout, mais je me serai attendu à ce qu'une valeur réelle mesurée de k soit fournie, car on pourrait rétorquer être en présence d'une résolution en temps exponentiel mais tellement rapide qu'on a l'impression d'un temps polynomial.

[invite4492c379]

(...)

C'est dommage et ça gâche un peu tout, mais j'aurais aimé que la valeur mesurée de k soit fournie, car on pourrait rétorqué qu'on est en présence d'une résolution en temps exponentiel mais tellement rapide qu'on a l'impression d'un temps polynomial.

Il n'y a eu aucune mesure, les auteurs disent juste qu'il est raisonnable de penser que construire un dispositif se fait en O(n^k) ; En quoi la mesure est-elle importante ?

[invite7863222222222]

Il n'y a eu aucune mesure, les auteurs disent juste qu'il est raisonnable de penser que construire un dispositif se fait en O(n^k)

Ils ne parlent pas du temps pour construire un dispositif mais du temps après lequel le système est dans l'état correspondant à la longueur minimale du graphe passant par les n points.

Raisonnable ou pas, c'est de la physique donc l'expérience est prioritairement apte à dire ce qu'il en ait, non ?

(Ceci dit, je n'ai pas plus de raison de croire le contraire, mais si on ne veut pas rester dans les mathématiques, mais aussi ancrer les propos dans la physique, comme semblent vouloir le faire les auteurs, la mesure me semble importante).

[invite4492c379]

Ils ne parlent pas du temps pour construire un dispositif mais du temps après lequel le système est dans l'état correspondant à la longueur minimale du graphe passant par les n points.

Raisonnable ou pas, c'est de la physique donc l'expérience est prioritairement apte à dire ce qu'il en ait, non ?

(Ceci dit, je n'ai pas plus de raison de croire le contraire, mais si on ne veut pas rester dans les mathématiques, mais aussi ancrer les propos dans la physique, comme semblent vouloir le faire les auteurs, la mesure me semble importante).

Il faut penser en terme d'algorithmes ...

En gros si on suit leur démarche pour STP(n), quelle que soit la valeur de n :

* construire le dispositif est une opération en O(n^k) ; cela me semble raisonnable, il faut au moins lire les coordonnées des n points (donc on est au minimum en O(n), k>1), prendre des mesures et placer les points (opérations à temps constant)
* plonger puis retirer le dispositif sont des opérations à temps constant donc en O(1) ; cela me semble tout autant raisonnable

Donc l'algorithme physique B(STP) a bien un comportement polynomial par rapport à la taille du problème.

On s'en moque de la valeur effective de k ou d'autres constantes, l'important c'est le comportement.

Maintenant leur raisonnement peut s'avérer faux, ce que les auteurs évoquent avec malice ; mais vrai ou faux il faut juste en comprendre les conséquences.