Ca dépend. Pour moi, si quelqu'un prouve que P=NP, il y a de fortes chances que la démonstration se fasse autrement qu'en trouvant un moyen "magique" de réduire tous les problèmes... ;)
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 (pour rappel NP ne veu pas dire non polynomial, mais non solvable polynomialement, ie on enpeut pas trouver de solutions par une approche polynomiale, mais la solution peut elle etre polynomiale).
De plus en passant par les algo de reduction dont parle Boubou on peut "extraire" une solution polynomiale a n'importe quel probleme NP complet a partir d'une solution d'un probleme NP complet donne.
En d'autres termes si on trouve un jour une solution polynomiale a un probleme NP complet, tous les problemes NP complet seront resolu dans la foulee avec une solution polynomiale pour chacun.
[^] # Re: Droit d'auteur et travailleurs
Posté par Jerome Herman . En réponse à la dépêche Droit d'auteur et travailleurs. Évalué à 1.
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 (pour rappel NP ne veu pas dire non polynomial, mais non solvable polynomialement, ie on enpeut pas trouver de solutions par une approche polynomiale, mais la solution peut elle etre polynomiale).
De plus en passant par les algo de reduction dont parle Boubou on peut "extraire" une solution polynomiale a n'importe quel probleme NP complet a partir d'une solution d'un probleme NP complet donne.
En d'autres termes si on trouve un jour une solution polynomiale a un probleme NP complet, tous les problemes NP complet seront resolu dans la foulee avec une solution polynomiale pour chacun.
Kha