Bonjour,
Un algorithme NP s'exécute en temps NP.
* Lorsque la complexité du problème NP croît, le temps NP de résolution peut-il être constant ?
** Peut-on mesurer le temps NP de résolution, car j'ai parfois l'impression que c'est comme essayer de mesurer une courbe en ayant qu'un seul point de celle-ci.
Merci.
une fonction constante est bien un polynôme.Envoyé par Noress
Il me semble utile de préciser les notions par un exemple:
Considérons on problème NP non P, ou du moins réputé tel (si vous parvenez à le démontrer ou à démontrer le contraire , il y a un million de dollars pour vous).
Le coloriage d'un graphe en 3 couleurs.
Il est évident que plus votre graphe sera important, plus le temps de calcul sera long pour trouver un coloriage ou prouver que c'est impossible. Le temps de calcul dépend donc de l'instance (le graphe) du problème
On ne connait pour cela pour l'instant que des algorithmes de complexité exponentielle pour ce problème, c'est à dire pour les quels le temps de calcul maximum en fonction de la taille du graphe est exponentiel.
La complexité d'un problème ou plus simplement d'un algorithme est donc une fonction de la taille des données.
Il est souvent difficile de déterminer la complexité d'un algorithme, et plus encore celle d'un problème, qui est celle des meilleurs algorithmes le résolvant.
