Algorithme d'énumération

Les algorithmes d’énumération sont des algorithmes qui ont pour but de calculer ou afficher une liste de toutes les réponses à un problème donné ; alors que les algorithmes « classiques » cherchent plutôt une solution (problèmes d’optimisation) ou à tester la vérité d’une affirmation (problèmes de décision). Par exemple, un algorithme listant toutes les cliques d’un graphe est un algorithme d’énumération.

Cette distinction est faite pour pouvoir construire des classes de complexité propres aux problèmes d’énumération. Par exemple, la classe PolynomialDelay des algorithmes d’énumérations dont le temps entre l’affichage de deux résultats est borné par un polynôme en la taille de l’entrée.

Classes de complexité

TotalP

La classe TotalP est la classe des problèmes dont les solutions peuvent être énumérées en temps polynomial en $n+m$ , où $n$ est la taille de l’entrée, et $m$ celle de la sortie. Elle est un cas particulier de classe de complexité paramétrée, où le paramètre est la taille de la sortie.

IncrementalPolynomial

IncrementalPolynomial est la classe des problèmes dont on il existe un algorithme qui prennent un temps polynomial en $k+n$ entre l’affichage de la $k$ -ième et la $(k+1)$ -ième solutions, où $n$ est la taille de l’entrée.

Pour montrer qu’un algorithme résout un problème d’énumération en temps IncrementalPolynomial, il est préférable de lui imposer de ne pas répéter plusieurs fois la même solution. Autrement, s'il peut trouver la première solution en temps polynomial, il lui suffit de répéter régulièrement une solution qu’il a déjà trouvée pendant qu’il en cherche une autre, ce qui réduirait l’intérêt de cette classe.

PolynomialDelay

Cette classe regroupe les problèmes pour lesquels il est possible d’énumérer les solutions de façon que le temps entre l’affichage de deux solutions soit borné par un polynôme en la taille de l’entrée. Elle est donc incluse dans IncrementalPolynomial.

Les problèmes dans P et dont l’ensemble des solutions est un matroïde sont en général dans cette classe. En effet, puisqu’ils sont dans P, on peut trouver une solution en temps polynomial ; et à partir de celle-ci on peut engendrer toutes les solutions par échange et hérédité.