Problema de distinción de elementos

En la teoría de la complejidad computacional , el problema de distinción de elementos o 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 se puede resolver ordenando la lista y luego verificando si hay elementos iguales consecutivos; También se puede resolver en un 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 puede encontrarse rápidamente después de resolver el problema en cuestión.

Complejidad del árbol de decisión

El número de comparaciones necesarias para resolver el problema de tamaño , en un modelo de cálculo basado en comparaciones, como un árbol de decisión o un árbol de decisión algebraico , es . Aquí, se invoca la notación theta grande , lo que significa que el problema se puede resolver en un número de comparaciones proporcionales a (una función linealítmica ) y que todas las soluciones requieren tantas 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 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 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 real de la RAM

Si los elementos del problema son números reales , el límite inferior del árbol de decisión se extiende al modelo de máquina real de acceso aleatorio con un conjunto de instrucciones que incluye suma, resta y multiplicación de números reales, así como comparación y división o resto ( "piso"). ^[5] De ello se deduce que la complejidad del problema en este modelo también es . Este modelo de RAM cubre más algoritmos que el modelo de árbol de decisión algebraico, ya que abarca algoritmos que utilizan indexación en tablas. Sin embargo, en este modelo se cuentan todos los pasos del programa, no sólo 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 el tiempo O ( n ² m ( m +2–log n )) , mientras que en una máquina no determinista la complejidad temporal es O ( n m ( n + log m )) . ^[6]

Complejidad cuántica

Los algoritmos cuánticos pueden resolver este problema más rápido en las consultas. El algoritmo óptimo es el de Andris Ambainis . ^[7] Yaoyun Shi demostró por primera vez un límite inferior ajustado 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 ocurren más de veces en un conjunto múltiple de tamaño se pueden encontrar en el tiempo mediante un algoritmo basado en comparación, el algoritmo de pesos pesados ​​de Misra-Gries . 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 decisión. ^[11] ${\displaystyle n/k}$ ${\displaystyle n}$ ${\displaystyle O(n\log k)}$ ${\displaystyle k=n}$

Ver también

• problema de colisión

Referencias

1. Gil, J.; Meyer auf der Heide, F.; Wigderson, A. (1990), "No todas las claves se pueden codificar 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 de á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 aleatorio sobre campos característicos cero", Complejidad computacional , 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 algebraicas de acceso aleatorio", 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 caminata cuántica 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 informática . 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 alcance 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", Ciencia de la programación informática , 2 (2): 143–152, doi :10.1016/0167-6423(82)90012-0, hdl : 1813/6345.