Algorithme d'énumération

La classe TotalP est la classe des problèmes dont les solutions peuvent être énumérées en temps polynomial en ${\displaystyle n+m}$, où ${\displaystyle n}$ est la taille de l’entrée, et ${\displaystyle 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 est la classe des problèmes dont on il existe un algorithme qui prennent un temps polynomial en ${\displaystyle k+n}$ entre l’affichage de la ${\displaystyle k}$-ième et la ${\displaystyle (k+1)}$-ième solutions, où ${\displaystyle 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.

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é.

• DOI On generating all maximal independent sets

• Portail de l'informatique théorique