Tu n'y es pas. On prouve qu'un problème est NP complet en trouvant une transformation d'un problème dont on sait qu'il est NP-complet en notre problème, avec une transfo qui a de bonne propriétés, la transformation doit s'effectuer en temps polynomial.
En gros ça implique que le problème est suffisamment complexe pour pouvoir exprimer un autre problème dont on connait la difficulté.
Du coup si tu trouves un algorithme polynomial pour UN problème NP complet, tu trouves un algorithme polynomial pour ... tous les problèmes NP complet, en appliquant en préprocessing les transformations des preuves des problèmes en autre problème jusqu'à tomber sur celui pour lequel tu as un algo :)
Comme les transformations sont polynomiales, l'agorithme résultant l'est aussi, CQFD. On sait aussi qu'il existe ce type de transformations pour tous les problèmes NP-complets entre eux.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par thoasm . En réponse au journal P != NP : la preuve. Évalué à 3.
En gros ça implique que le problème est suffisamment complexe pour pouvoir exprimer un autre problème dont on connait la difficulté.
Du coup si tu trouves un algorithme polynomial pour UN problème NP complet, tu trouves un algorithme polynomial pour ... tous les problèmes NP complet, en appliquant en préprocessing les transformations des preuves des problèmes en autre problème jusqu'à tomber sur celui pour lequel tu as un algo :)
Comme les transformations sont polynomiales, l'agorithme résultant l'est aussi, CQFD. On sait aussi qu'il existe ce type de transformations pour tous les problèmes NP-complets entre eux.