une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource
Une classe de complexité regroupe les problèmes de même complexité, souvent à une réduction polynomiale près.
Les classes usuelles sont définies en utilisant les machines de Turing comme modèles de calcul et les ressources sont le temps et l'espace
Souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité O(f(n)) de ressources du type R, où n, est la taille de l'entrée
4 familles:
TIME(t(n)): La classe des problèmes de décision qui peuvent être résolus en temps de l'ordre de grandeur de t(n) sur une machine déterministe
NTIME(t(n)): La classe des problèmes de décision qui peuvent être résolus en temps de l'ordre de grandeur de t(n) sur une machine non déterministe
SPACE(s(n)): La classe des problèmes de décision qui requièrent pour être résolus un espace de l'ordre de grandeur de s(n) sur une machine déterministe
NSPACE(s(n)): La classe des problèmes de décision qui requièrent pour être résolus un espace de l'ordre de grandeur de s(n) sur une machine non déterministe.
Classes en temps:
P:
Classe des problèmes décidés en temps polynomial par une machine déterministe.
Ces problèmes sont souvent considérés comme ceux pour lesquels il existe un algorithme efficace (voir la thèse de Cobham) ;
NP:
Classe des problèmes décidés en temps polynomial par une machine non déterministe (ainsi que la classe complémentaire, co-NP) ;
EXPTIME:
Classe des problèmes décidés en temps exponentiel par une machine déterministe ;
NEXPTIME:
Classe des problèmes décidés en temps exponentiel par une machine non-déterministe.
Classes en espace:
L:
Classe des problèmes qui peuvent être résolus en espace logarithmique sur une machine déterministe ;
NL:
Classe des problèmes qui peuvent être résolus en espace logarithmique sur une machine non-déterministe ;
PSPACE:
Classe des problèmes qui peuvent être résolus en espace polynomial sur une machine déterministe.
En fait cette classe est égale à NPSPACE d'après le théorème de Savitch ;
EXPSPACE:
Classe des problèmes qui peuvent être résolus en espace exponentiel
Problème C-complet ou C-difficile:
Un problème est C-difficile si ce problème est au moins aussi difficile que tous les problèmes dans C
Un problème C-difficile qui appartient à C est dit C-complet
Dans beaucoup de cas on s'intéresse aux réductions polynomiales, c'est-à-dire celle demandant uniquement un espace et un temps polynomial pour être effectuée
mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat
le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas
on utilise couramment les notations grand O de Landau
La complexité en temps étant la mesure la plus courante en algorithmique, on parle parfois simplement de la complexité d'un algorithme
Définition:
plusieurs façons de définir ces étapes:
nombre d'opérations dans une machine RAM
mesures plus théoriques comme le nombre de comparaisons dans le cas d'un algorithme de tri
nombre de pas d'une machine de Turing
Le temps, comme défini plus haut, est lié au temps de calcul réel mais c'est une mesure plus abstraite, qui dépend de l'algorithme et de l'entrée mais est indépendante de la puissance de l'ordinateur par exemple (on compte des étapes de calcul et non des secondes)
Mesure de l'espace utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée.
L'espace compte le nombre maximum de cases mémoire utilisées simultanément pendant un calcul
Usuellement l'espace que l'on prend en compte lorsque l'on parle de l'espace nécessaire pour les entrées de taille n, est l'espace le plus grand pour les entrées de cette taille ; on parle de complexité en espace dans le pire cas
On utilise couramment les notations grand O de Landau
problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP)
Est un problème de décision
Vérifie les propriétés suivantes :
il est possible de vérifier une solution efficacement (en temps polynomial)
la classe des problèmes vérifiant cette propriété est notée NP ;
tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale
cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de la classe NP.
Un problème NP-difficile est un problème qui remplit la seconde condition
Résolution:
Bien qu'on puisse vérifier rapidement toute solution proposée d'un problème NP-complet, on ne sait pas en trouver efficacement
Tous les algorithmes connus pour résoudre des problèmes NP-complets ont un temps d'exécution exponentiel en la taille des données d'entrée dans le pire des cas, et sont donc inexploitables en pratique même pour des instances de taille modérée
Savoir que le problème sur lequel on travaille est NP-complet est une indication du fait que le problème est difficile à résoudre, donc qu'il vaut mieux chercher des solutions approchées en utilisant des algorithmes d'approximation ou utiliser des heuristiques pour trouver des solutions exactes
