Ca ne depend pas, il est prouve (mathematiquement) que si un probleme NP complet a une solution polynomiale, alors tous les problemes NP complet ont une solution polynomiale
Tu n'as pas compris ce que je voulais dire. Ce n'est pas parce qu'on a prouvé que P=NP qu'on a trouvé une solution polynomiale à un problème NP-complet. On a simplement pu démontrer son existence par des moyens détournés, sans exhiber une solution précise au problème.
De plus, le débat P=NP n'est pas très intéressant en pratique. Ce n'est pas parce qu'un problème est connu comme acceptant une résolution en temps polynomial, que l'algorithme trouvé par les moyens de réduction est acceptable (s'il est en O(n^8) avec une énorme constante multiplicative, tu conviendras que c'est pas génial). Comme Boubou, tu confonds la prouvabilité d'une propriété (il existe une méthode en temps polynomial) avec l'exhibition d'une solution intéressante en pratique (je sais décrire une méthode qui convient dans les cas considérés). Cette divergence des objectifs prouve bien, à mon sens, que les mathématiques appliquées et l'informatique sont deux disciplines séparées. C'est un peu comme la différence entre physique des matériaux et architecture.
Du reste, intuitivement, P=NP est une utopie. C'est comme l'existence de Dieu : même si on n'a aucune preuve la niant, il est raisonnable de ne pas y croire...
[^] # Re: Droit d'auteur et travailleurs
Posté par Moby-Dik . En réponse à la dépêche Droit d'auteur et travailleurs. Évalué à 1.
Tu n'as pas compris ce que je voulais dire. Ce n'est pas parce qu'on a prouvé que P=NP qu'on a trouvé une solution polynomiale à un problème NP-complet. On a simplement pu démontrer son existence par des moyens détournés, sans exhiber une solution précise au problème.
De plus, le débat P=NP n'est pas très intéressant en pratique. Ce n'est pas parce qu'un problème est connu comme acceptant une résolution en temps polynomial, que l'algorithme trouvé par les moyens de réduction est acceptable (s'il est en O(n^8) avec une énorme constante multiplicative, tu conviendras que c'est pas génial). Comme Boubou, tu confonds la prouvabilité d'une propriété (il existe une méthode en temps polynomial) avec l'exhibition d'une solution intéressante en pratique (je sais décrire une méthode qui convient dans les cas considérés). Cette divergence des objectifs prouve bien, à mon sens, que les mathématiques appliquées et l'informatique sont deux disciplines séparées. C'est un peu comme la différence entre physique des matériaux et architecture.
Du reste, intuitivement, P=NP est une utopie. C'est comme l'existence de Dieu : même si on n'a aucune preuve la niant, il est raisonnable de ne pas y croire...