Je vais encore me ridiculiser!
Mais bon, essayons de trouver ce que j'ai mal compris.
La classe NPC représente les problèmes vers lesquels tous les problème de classe NP peuvent être réduits en temps polynomiale.
Supposons par exemple que le problème SAT appartenant à la classe NPC ait une complexité en temps O(2^n).
Et que le problème du voyageur de commerce qui appartient aussi à la classe NPC nécessite un temps de complexité O(n!).
Selon la définition de NPC et puisque NPC est inclus dans NP on doit pouvoir réduire le problème du voyageur de commerce en temps polynomial vers SAT et vice versa.
Ce qui équivaut à dire que l'on peut résoudre le problème du voyageur avec un temps O(2^n) plus un temps polynomiale demandé par la réduction.
Cela me semble être en contradiction partielle avec le O(n!) du voyageur de commerce, car comment le temps polynomial de la reduction peut-il augmenter le temps total à un niveau factoriel?
Aucun commentaire:
Enregistrer un commentaire