Je viens de piger: c'est simplement la définition de "NP complet" qui exige que tous ces problèmes soient équivalents. C'est donc en fait un seul problème.
Je n'avais pas saisi que "NP" n'est pas la même chose que "NP complet".
Je reprends alors, vous corrigez si c'est idiot:
- résoudre n'importe quel problème NP-complet revient à résoudre tous les NP-complets (puisqu'en fait c'est la même chose)
- résoudre n'importe quel problème NP n'amène rien pour les autres (sauf découverte d'une grosse astuce)
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Kerro . En réponse au journal P != NP : la preuve. Évalué à 3.
Je n'avais pas saisi que "NP" n'est pas la même chose que "NP complet".
Je reprends alors, vous corrigez si c'est idiot:
- résoudre n'importe quel problème NP-complet revient à résoudre tous les NP-complets (puisqu'en fait c'est la même chose)
- résoudre n'importe quel problème NP n'amène rien pour les autres (sauf découverte d'une grosse astuce)