En fait c'est un poil plus compliqué que ça, certains problèmes NP comme la factorisation en nombre premiers n'ont pas de telles transformations (lu dans le dernier numéro HS de pour la Science sur l'informatique quantique), ne sont pas forcément NP-complets et n'ont pas de réduction polynomiale vers un problème de NP ...
[^] # Re: Il dit qu'il est pas d'accord.
Posté par thoasm . En réponse au journal P != NP : la preuve. Évalué à 4.
http://fr.wikipedia.org/wiki/D%C3%A9composition_en_produit_d(...)
Je sais pas si la preuve traîte de ce problème ou de ce type de problème, à voir :)