classe de complexité

INFORMATIQUE

Une classe de complexité de problèmes est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d’une certaine ressource

Par exemple, un problème est dit polynomial s’il existe un algorithme y répondant dont la complexité est asymptotiquement dominée par un polynôme.