Dans la théorie de la complexité computationnelle, une réduction en temps polynomial est une méthode pour résoudre un problème en utilisant un autre. Les réductions en temps polynomial sont fréquemment utilisées dans la théorie de la complexité pour définir à la fois des classes de complexité et des problèmes complets pour ces classes. …
Qu'est-ce qu'un temps polynomial ?
Un algorithme est dit en temps polynomial si son temps d'exécution est majoré par une expression polynomiale dans la taille de l'entrée de l'algorithme, c'est-à-dire T(n)=O(nk) pour une constante positive k.
Comment savoir si quelque chose est un temps polynomial ?
3 Réponses. Un algorithme est polynomial (a un temps d'exécution polynomial) si pour un certain k, C>0, son temps d'exécution sur des entrées de taille n est au plus Cnk. De manière équivalente, un algorithme est polynomial si pour un certain k>0, son temps d'exécution sur des entrées de taille n est O(nk).
Que se passe-t-il si la réduction est autorisée en temps exponentiel ?
Si la réduction est autorisée en temps exponentiel, alors elle peut résoudre complètement le problème d'origine et produire une instance triviale du problème cible Cela signifie que chaque problème dans NP est réductible à chaque autre problème par ce type de réductions, donc tout problème dans NP est NP-complet pour des réductions de temps exponentielles.
Qu'est-ce qu'un algorithme exponentiel ?
Un algorithme est dit en temps exponentiel, si T(n) est majoré par 2poly( ) , où poly(n) est un polynôme de n. Plus formellement, un algorithme est un temps exponentiel si T(n) est borné par O(2nk) pour une constante k. Ref:Wiki.
