En général pour prouver qu'un problème X est NP-complet, tu montres qu'il est équivalent à un autre problème Y qui est NP-complet à une transformation polynomiale près.
Donc si tu as un algo pour résoudre le problème Y en temps polynomial, il suffit d'appliquer une transformation polynomiale et tu peut résoudre le problème X.
Je vais faire une analogie foireuse mais qui j'espère permet de comprendre : Image que faire "a+b" soit NP-complet et que faire "-b" soit polynomial. Dans ce cas là, faire "a-b" est NP complet car avec une transformation polynomiale tu peut passer d'un problème à l'autre.
Donc si tu trouve un moyen de faire "a+b" est temps polynomial, tu sais aussi faire "a-b" en temps polynomial. (j'avais prévenu que l'analogie était foireuse...)
Le truc là dedans c'est justement que prouver qu'un problème est NP-complet par équivalence à un autre problème est beaucoup plus simple que faire la preuve depuis zero, donc quasiment toutes les preuves de NP-completude sont faites comme cela.
Et s'il existe des problèmes pour lesquels on à pas de réduction connues (à ma connaissance il n'y en as pas) la théorie nous dit que de toute façon elle existe, donc il suffit de ce mettre au boulot... Et vu l'expressivité de problèmes tel que le voyageur de commerce ou 3-SAT, il y a beaucoup de cas ou ce n'est pas si dur.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par beagf . En réponse au journal P != NP : la preuve. Évalué à 4.
En général pour prouver qu'un problème X est NP-complet, tu montres qu'il est équivalent à un autre problème Y qui est NP-complet à une transformation polynomiale près.
Donc si tu as un algo pour résoudre le problème Y en temps polynomial, il suffit d'appliquer une transformation polynomiale et tu peut résoudre le problème X.
Je vais faire une analogie foireuse mais qui j'espère permet de comprendre : Image que faire "a+b" soit NP-complet et que faire "-b" soit polynomial. Dans ce cas là, faire "a-b" est NP complet car avec une transformation polynomiale tu peut passer d'un problème à l'autre.
Donc si tu trouve un moyen de faire "a+b" est temps polynomial, tu sais aussi faire "a-b" en temps polynomial. (j'avais prévenu que l'analogie était foireuse...)
Le truc là dedans c'est justement que prouver qu'un problème est NP-complet par équivalence à un autre problème est beaucoup plus simple que faire la preuve depuis zero, donc quasiment toutes les preuves de NP-completude sont faites comme cela.
Et s'il existe des problèmes pour lesquels on à pas de réduction connues (à ma connaissance il n'y en as pas) la théorie nous dit que de toute façon elle existe, donc il suffit de ce mettre au boulot... Et vu l'expressivité de problèmes tel que le voyageur de commerce ou 3-SAT, il y a beaucoup de cas ou ce n'est pas si dur.