Problema de distinción de elementos

En la teoría de la complejidad computacional , el problema de distinción de elementos o el problema de unicidad de elementos es el problema de determinar si todos los elementos de una lista son distintos.

Es un problema bien estudiado en muchos modelos diferentes de computación. El problema puede resolverse ordenando la lista y luego verificando si hay elementos iguales consecutivos; también puede resolverse en tiempo esperado lineal mediante un algoritmo aleatorio que inserta cada elemento en una tabla hash y compara solo aquellos elementos que se colocan en la misma celda de la tabla hash. ^[1]

Se demuestran varios límites inferiores en la complejidad computacional reduciendo el problema de distinción de elementos al problema en cuestión, es decir, demostrando que la solución del problema de unicidad de elementos se puede encontrar rápidamente después de resolver el problema en cuestión.

Complejidad del árbol de decisiones

El número de comparaciones necesarias para resolver el problema de tamaño , en un modelo de cálculo basado en comparación, como un árbol de decisión o un árbol de decisión algebraico , es . Aquí, invoca la notación theta grande , lo que significa que el problema se puede resolver en un número de comparaciones proporcional a (una función lineal-ítmica ) y que todas las soluciones requieren esta cantidad de comparaciones. ^[2] En estos modelos de cálculo, los números de entrada no se pueden usar para indexar la memoria de la computadora (como en la solución de la tabla hash), sino que solo se puede acceder a ellos calculando y comparando funciones algebraicas simples de sus valores. Para estos modelos, un algoritmo basado en la clasificación por comparación resuelve el problema dentro de un factor constante del mejor número posible de comparaciones. El mismo límite inferior se aplica también al número esperado de comparaciones en el modelo de árbol de decisión algebraico aleatorio . ^{[3] [4]} ${\displaystyle n}$ ${\displaystyle \Theta (n\log n)}$ ${\displaystyle \Theta }$ ${\displaystyle n\log n}$

Complejidad de la RAM real

Si los elementos del problema son números reales , el límite inferior del árbol de decisiones se extiende al modelo de máquina de acceso aleatorio real con un conjunto de instrucciones que incluye la suma, resta y multiplicación de números reales, así como la comparación y la división o el resto ("floor"). ^[5] De ello se deduce que la complejidad del problema en este modelo también es . Este modelo RAM cubre más algoritmos que el modelo de árbol de decisiones algebraico, ya que abarca algoritmos que utilizan la indexación en tablas. Sin embargo, en este modelo se cuentan todos los pasos del programa, no solo las decisiones. ${\displaystyle \Theta (n\log n)}$

Complejidad de la máquina de Turing

Una máquina de Turing determinista de cinta única puede resolver el problema, para n elementos de m ≥ log n bits cada uno, en un tiempo O ( n ² m ( m +2–log n )) , mientras que en una máquina no determinista la complejidad temporal es O ( nm ( n + log m )) . ^[6]

Complejidad cuántica

Los algoritmos cuánticos pueden resolver este problema más rápidamente, en consultas. El algoritmo óptimo es de Andris Ambainis . ^[7] Yaoyun Shi fue el primero en demostrar un límite inferior estricto cuando el tamaño del rango es suficientemente grande. ^[8] Ambainis ^[9] y Kutin ^[10] de forma independiente (y mediante diferentes pruebas) ampliaron su trabajo para obtener el límite inferior para todas las funciones. ${\textstyle \Theta (n^{2/3})}$

Generalización: Encontrar elementos repetidos

Los elementos que aparecen más de veces en un conjunto múltiple de tamaño se pueden encontrar mediante un algoritmo basado en comparación, el algoritmo de Misra-Gries Heavy Hitters , en el tiempo . El problema de distinción de elementos es un caso especial de este problema donde . Este tiempo es óptimo según el modelo de cálculo del árbol de decisiones. ^[11] ${\displaystyle n/k}$ ${\displaystyle n}$ ${\displaystyle O(n\log k)}$ ${\displaystyle k=n}$

Véase también

• Problema de colisión

Referencias

1. Gil, J.; Meyer auf der Heide, F.; Wigderson, A. (1990), "No todas las claves pueden ser cifradas en tiempo constante", Proc. 22.º Simposio ACM sobre teoría de la computación , págs. 244-253, doi : 10.1145/100216.100247 , S2CID  11943779.
2. Ben-Or, Michael (1983), "Límites inferiores para árboles de cálculo algebraico", Proc. 15.º Simposio ACM sobre teoría de la computación , págs. 80-86, doi : 10.1145/800061.808735.
3. Grigóriev, Dima ; Karpinski, Marek ; Heide, Friedhelm Meyer; Smolensky, Roman (1996), "Un límite inferior para árboles de decisión algebraicos aleatorios", Computational Complexity , 6 (4): 357, doi :10.1007/BF01270387, S2CID  1462184.
4. Grigoriev, Dima (1999), "Límites inferiores de complejidad para árboles de cálculo aleatorios sobre campos de características cero", Computational Complexity , 8 (4): 316–329, doi :10.1007/s000370050002, S2CID  10641238.
5. Ben-Amram, Amir M.; Galil, Zvi (2001), "Límites inferiores topológicos en máquinas de acceso aleatorio algebraico", SIAM Journal on Computing , 31 (3): 722–761, doi :10.1137/S0097539797329397.
6. Ben-Amram, Amir M.; Berkman, Omer; Petersen, Holger (2003), "Distinción de elementos en máquinas de Turing de una cinta: una solución completa.", Acta Informatica , 40 (2): 81–94, doi :10.1007/s00236-003-0125-8, S2CID  24821585
7. Ambainis, Andris (2007), "Algoritmo de paseo cuántico para la distinción de elementos", SIAM Journal on Computing , 37 (1): 210–239, arXiv : quant-ph/0311001 , doi :10.1137/S0097539705447311
8. Shi, Y. (2002). Límites inferiores cuánticos para los problemas de colisión y distinción de elementos . Actas del 43.° Simposio sobre Fundamentos de la Ciencia de la Computación . págs. 513–519. arXiv : quant-ph/0112086 . doi :10.1109/SFCS.2002.1181975.
9. Ambainis, A. (2005). "Grado polinomial y límites inferiores en complejidad cuántica: colisión y distinción de elementos con rango pequeño". Teoría de la computación . 1 (1): 37–46. doi : 10.4086/toc.2005.v001a003 .
10. Kutin, S. (2005). "Límite inferior cuántico para el problema de colisión con rango pequeño". Teoría de la computación . 1 (1): 29–36. doi : 10.4086/toc.2005.v001a002 .
11. Misra, J.; Gries, D. (1982), "Encontrar elementos repetidos", Science of Computer Programming , 2 (2): 143–152, doi :10.1016/0167-6423(82)90012-0, hdl : 1813/6345.