Problème de distinction des éléments

Dans la théorie de la complexité informatique , le problème de distinction des éléments ou problème d'unicité des éléments est le problème consistant à déterminer si tous les éléments d'une liste sont distincts.

Il s'agit d'un problème bien étudié dans de nombreux modèles de calcul différents. Le problème peut être résolu en triant la liste puis en vérifiant s'il y a des éléments consécutifs égaux ; il peut également être résolu en temps linéaire attendu par un algorithme randomisé qui insère chaque élément dans une table de hachage et compare uniquement les éléments qui sont placés dans la même cellule de la table de hachage.

Plusieurs limites inférieures de la complexité de calcul sont prouvées en réduisant le problème de distinction des éléments au problème en question, c'est-à-dire en démontrant que la solution du problème d'unicité des éléments peut être rapidement trouvée après avoir résolu le problème en question.

Le nombre de comparaisons nécessaires pour résoudre le problème de taille , dans un modèle de calcul basé sur la comparaison tel qu'un arbre de décision ou un arbre de décision algébrique , est . Ici, invoque la notation thêta grande , ce qui signifie que le problème peut être résolu en un nombre de comparaisons proportionnel à (une fonction linéarithmique ) et que toutes les solutions nécessitent ce nombre de comparaisons. Dans ces modèles de calcul, les nombres d'entrée ne peuvent pas être utilisés pour indexer la mémoire de l'ordinateur (comme dans la solution de la table de hachage) mais ne peuvent être consultés qu'en calculant et en comparant des fonctions algébriques simples de leurs valeurs. Pour ces modèles, un algorithme basé sur le tri par comparaison résout le problème dans un facteur constant du meilleur nombre possible de comparaisons. La même limite inférieure s'applique également au nombre attendu de comparaisons dans le modèle d'arbre de décision algébrique randomisé .

Si les éléments du problème sont des nombres réels , la borne inférieure de l'arbre de décision s'étend au modèle de machine à accès aléatoire réel avec un jeu d'instructions qui comprend l'addition, la soustraction et la multiplication de nombres réels, ainsi que la comparaison et la division ou le reste (« floor »). Il s'ensuit que la complexité du problème dans ce modèle est également . Ce modèle RAM couvre plus d'algorithmes que le modèle d'arbre de décision algébrique, car il englobe les algorithmes qui utilisent l'indexation dans des tables. Cependant, dans ce modèle, toutes les étapes du programme sont comptées, pas seulement les décisions.

Une machine de Turing déterministe à bande unique peut résoudre le problème, pour n éléments de m ≥ log n bits chacun, en temps O ( n ² m ( m +2–log n )) , tandis que sur une machine non déterministe la complexité temporelle est O ( nm ( n + log m )) .

Les algorithmes quantiques peuvent résoudre ce problème plus rapidement, dans les requêtes. L'algorithme optimal est celui d' Andris Ambainis . Yaoyun Shi a d'abord prouvé une limite inférieure stricte lorsque la taille de la plage est suffisamment grande. Ambainis et Kutin ont indépendamment (et via des preuves différentes) étendu son travail pour obtenir la limite inférieure pour toutes les fonctions.

Les éléments qui apparaissent plus de fois dans un multi-ensemble de taille peuvent être trouvés par un algorithme basé sur la comparaison, l' algorithme des poids lourds de Misra-Gries , en temps . Le problème de distinction des éléments est un cas particulier de ce problème où . Ce temps est optimal sous le modèle d'arbre de décision du calcul.