¿Existe un algoritmo para resolver el problema 3SUM a tiempo? , para algunos ?
En la teoría de la complejidad computacional , el problema 3SUM pregunta si un conjunto dado delos números reales contienen tres elementos que suman cero. Una versión generalizada, k -SUM, hace la misma pregunta sobre k números. 3SUM se puede resolver fácilmente en tiempo y coincidencia los límites inferiores se conocen en algunos modelos especializados de cálculo ( Erickson 1999 ).
Se conjeturaba que cualquier algoritmo determinista para el 3SUM requiere hora. En 2014, la conjetura original de 3SUM fue refutada por Allan Grønlund y Seth Pettie, quienes dieron un algoritmo determinista que resuelve 3SUM enhora. [1] Además, Grønlund y Pettie demostraron que la complejidad del árbol de decisión de 4 líneas lineales de 3SUM es. Estos límites se mejoraron posteriormente. [2] [3] [4] El algoritmo actual más conocido para 3SUM se ejecuta enhora. [4] Kane, Lovett y Moran demostraron que la complejidad del árbol de decisión 6 lineal de 3SUM es. [5] El último límite es estrecho (hasta un factor logarítmico). Todavía se conjetura que 3SUM no tiene solución entiempo esperado. [6]
Cuando los elementos son números enteros en el rango , 3SUM se puede resolver en tiempo representando el conjunto de entrada como un vector de bits , calculando el conjuntode todas las sumas por pares como una convolución discreta utilizando la transformada rápida de Fourier , y finalmente comparando este conjunto con. [7]
Algoritmo cuadrático
Suponga que la matriz de entrada es . En los modelos informáticos de números enteros ( RAM de palabras ), 3SUM se puede resolver en tiempo en promedio insertando cada número en una tabla hash , y luego para cada índice y , comprobando si la tabla hash contiene el entero .
También es posible resolver el problema al mismo tiempo en un modelo de computación basado en comparación o RAM real , para el cual no se permite el hash. El algoritmo a continuación primero ordena la matriz de entrada y luego prueba todos los pares posibles en un orden cuidadoso que evita la necesidad de realizar búsquedas binarias para los pares en la lista ordenada, logrando el peor de los casostiempo, como sigue. [8]
ordena);para i = 0 a n - 2 do a = S [i]; inicio = i + 1; final = n - 1; mientras (inicio)>hacer b = S [inicio] c = S [final]; si (a + b + c == 0) entonces salida a, b, c; // Continuar la búsqueda de todas las combinaciones de tripletes sumando cero. // Necesitamos actualizar tanto el final como el comienzo juntos ya que los valores de la matriz son distintos. inicio = inicio + 1; fin = fin - 1; más si (a + b + c> 0) entonces fin = fin - 1; demás inicio = inicio + 1; fin fin
El siguiente ejemplo muestra la ejecución de este algoritmo en una pequeña matriz ordenada. Los valores actuales de una se muestran en rojo, los valores de b y c se muestran en magenta.
-25 -10 -7 -3 2 4 8 10 (a + b + c == - 25) -25 -10 -7 -3 2 4 8 10 (a + b + c == - 22) . . . -25-10-7-3 2 4 8 10 (a + b + c == - 7) -25 -10 -7 -3 2 4 8 10 (a + b + c == - 7) -25 -10 -7 -3 2 4 8 10 (a + b + c == - 3) -25 -10 -7 -3 2 4 8 10 (a + b + c == 2) -25 -10 -7 -3 2 4 8 10 (a + b + c == 0)
La corrección del algoritmo se puede ver de la siguiente manera. Supongamos que tenemos una solución a + b + c = 0. Dado que los punteros solo se mueven en una dirección, podemos ejecutar el algoritmo hasta que el puntero del extremo izquierdo apunte a a. Ejecute el algoritmo hasta que uno de los punteros restantes apunte ab o c, lo que ocurra primero. Luego, el algoritmo se ejecutará hasta que el último puntero apunte al término restante, dando la solución afirmativa.
Variantes
Suma distinta de cero
En lugar de buscar números cuya suma sea 0, es posible buscar números cuya suma sea cualquier constante C de la siguiente manera:
- Reste C / 3 de todos los elementos de la matriz de entrada.
- En la matriz modificada, busque 3 elementos cuya suma sea 0.
Por ejemplo, si A = [1,2,3,4] y si se le pide que encuentre 3sum para C = 4, reste todos los elementos de A por 4/3 y resuélvalo de la forma habitual de 3sum, es decir, (aC / 3) + (bC / 3) + (cC / 3) = 0
O simplemente podría modificar el algoritmo original para buscar en la tabla hash el número entero (C - (S [i] + S [j])).
3 matrices diferentes
En lugar de buscar los 3 números en una sola matriz, podemos buscarlos en 3 matrices diferentes. Es decir, dados tres arreglos X, Y y Z, encuentre tres números a ∈ X , b ∈ Y , c ∈ Z , tales que. Llame a la variante de 1 matriz 3SUM × 1 y a la variante de 3 matrices 3SUM × 3.
Dado un solucionador para 3SUM × 1, el problema 3SUM × 3 se puede resolver de la siguiente manera (asumiendo que todos los elementos son números enteros):
- Para cada elemento en X , Y y Z , establezca:, , .
- Deje S ser una concatenación de las matrices X , Y y Z .
- Usa el oráculo 3SUM × 1 para encontrar tres elementos tal que .
- Regreso .
Por cierto transformamos las matrices, se garantiza que un ∈ X , b ∈ Y , c ∈ Z . [9]
Suma de convolución
En lugar de buscar elementos arbitrarios de la matriz como:
el problema de suma 3 de convolución (Conv3SUM) busca elementos en ubicaciones específicas: [10]
Reducción de Conv3SUM a 3SUM
Dado un solucionador para 3SUM, el problema Conv3SUM se puede resolver de la siguiente manera. [10]
- Defina una nueva matriz T , tal que para cada índice i :(donde n es el número de elementos de la matriz y los índices van de 0 an -1).
- Resolver 3SUM en la matriz T .
Prueba de corrección:
- Si en la matriz original hay un triple con , luego , Por lo que esta solución se puede encontrar en 3SUM T .
- Por el contrario, si en la nueva matriz hay un triple con , luego . Porque, necesariamente y , Así que esto es una solución válida para Conv3SUM en S .
Reducción de 3SUM a Conv3SUM
Dado un solucionador para Conv3SUM, el problema 3SUM se puede resolver de la siguiente manera. [6] [10]
La reducción utiliza una función hash . Como primera aproximación, suponga que tenemos una función hash lineal, es decir, una función h tal que:
Suponga que todos los elementos son números enteros en el rango: 0 ... N -1, y que la función h asigna cada elemento a un elemento en el rango más pequeño de índices: 0 ... n -1. Cree una nueva matriz T y envíe cada elemento de S a su valor hash en T , es decir, para cada x en S :
Inicialmente, suponga que las asignaciones son únicas (es decir, cada celda en T acepta solo un elemento de S ). Resolver Conv3SUM en T . Ahora:
- Si hay una solución para 3SUM: , luego: y , Por lo que esta solución va a ser encontrado por el solucionador Conv3SUM en T .
- A la inversa, si un Conv3SUM se encuentra en T , entonces, evidentemente, corresponde a una solución 3SUM en S desde T es sólo una permutación de S .
Esta solución idealizada no funciona, ya que cualquier función hash puede asignar varios elementos distintos de S a la misma celda de T . El truco consiste en crear una matriz T * seleccionando un solo elemento aleatorio de cada celda de T y ejecutar Conv3SUM en T * . Si se encuentra una solución, entonces es una solución correcta para 3SUM en S . Si no se encuentra una solución, cree un T * aleatorio diferente y vuelva a intentarlo. Supongamos que hay en la mayoría de los R elementos en cada celda de T . Entonces, la probabilidad de encontrar una solución (si existe una solución) es la probabilidad de que la selección aleatoria seleccione el elemento correcto de cada celda, que es. Ejecutando Conv3SUM veces, la solución se encontrará con una alta probabilidad.
Desafortunadamente, no tenemos hash lineal perfecto, por lo que tenemos que usar una función hash casi lineal , es decir, una función h tal que:
- o
Esto requiere duplicar los elementos de S al copiarlos en T , es decir, poner cada elemento ambos en (como antes) y en . Entonces cada celda tendrá 2 elementos R , y tendremos que ejecutar Conv3SUM veces.
3SUM-dureza
Un problema se denomina 3SUM-difícil si resolverlo en tiempo subcuadrático implica un algoritmo de tiempo subcuadrático para 3SUM. El concepto de dureza 3SUM fue introducido por Gajentaan y Overmars (1995) . Demostraron que una gran clase de problemas en geometría computacional son difíciles de 3SUM, incluidos los siguientes. (Los autores reconocen que muchos de estos problemas son aportados por otros investigadores).
- Dado un conjunto de líneas en el plano, ¿hay tres que se encuentran en un punto?
- Dado un conjunto de segmentos de línea paralelos a ejes que no se intersecan, ¿hay una línea que los separe en dos subconjuntos no vacíos?
- Dado un conjunto de franjas infinitas en el plano, ¿cubren completamente un rectángulo dado?
- Dado un conjunto de triángulos en el plano, calcula su medida.
- Dado un conjunto de triángulos en el plano, ¿su unión tiene un agujero?
- Varios problemas de visibilidad y planificación del movimiento, por ejemplo,
- Dado un conjunto de triángulos horizontales en el espacio, ¿se puede ver un triángulo en particular desde un punto en particular?
- Dado un conjunto de obstáculos de segmento de línea paralela de eje que no se cruzan en el plano, ¿se puede mover una varilla determinada mediante traslaciones y rotaciones entre las posiciones de inicio y finalización sin chocar con los obstáculos?
A estas alturas, hay una multitud de otros problemas que entran en esta categoría. Un ejemplo es la versión de decisión de la ordenación X + Y : dados conjuntos de números X e Y de n elementos cada uno, ¿hay n ² distintos x + y para x ∈ X , y ∈ Y ? [11]
Ver también
Notas
- ^ Grønlund y Pettie 2014 .
- ^ Freund, 2017 .
- ^ Gold y Sharir 2017 .
- ^ a b Chan, 2018 .
- ^ Kane, Lovett y Moran 2018 .
- ↑ a b Kopelowitz, Tsvi; Pettie, Seth; Porat, Ely (2014). "Dureza 3SUM en estructuras de datos (dinámicas)". arXiv : 1407,6756 [ cs.DS ].
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03384-4.Ex. 30.1–7, pág. 906.
- ^ Gráficos de visibilidad y suma 3 por Michael Hoffmann
- ^ Para una reducción en la otra dirección, consulte Variantes del problema de suma 3 .
- ^ a b c Patrascu, M. (2010). Hacia los límites inferiores del polinomio para problemas dinámicos . Actas del 42º simposio ACM sobre teoría de la computación - STOC '10. pag. 603. doi : 10.1145 / 1806689.1806772 . ISBN 9781450300506.
- ^ Demaine, Erik ; Erickson, Jeff; O'Rourke, Joseph (20 de agosto de 2006). "Problema 41: Clasificación X + Y (sumas por pares)" . El proyecto Open Problems . Consultado el 23 de septiembre de 2014 .
Referencias
- Kane, Daniel M .; Lovett, Shachar; Moran, Shay (2018). "Árboles de decisión lineal casi óptimos para k-SUM y problemas relacionados". Actas del 50º Simposio Anual ACM SIGACT sobre Teoría de la Computación (STOC) : 554–563. arXiv : 1705.01720 . doi : 10.1145 / 3188745.3188770 . ISBN 9781450355599.
- Chan, Timothy M. (2018), "Más aceleraciones de factores logarítmicos para 3SUM, (mediana, +) - Convolución y algunos problemas geométricos 3SUM-difíciles", Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos ( SODA) : 881–897, doi : 10.1137 / 1.9781611975031.57 , ISBN 978-1-61197-503-1
- Grønlund, A .; Pettie, S. (2014). Tríos, degenerados y triángulos amorosos . 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. pag. 621. arXiv : 1404.0799 . Código bibliográfico : 2014arXiv1404.0799G . doi : 10.1109 / FOCS.2014.72 . ISBN 978-1-4799-6517-5.
- Freund, Ari (2017), "Improved Subquadratic 3SUM", Algorithmica , 44 (2): 440–458, doi : 10.1007 / s00453-015-0079-6.
- Gold, Omer; Sharir, Micha (2017), "Límites mejorados para 3SUM, k -SUM y degeneración lineal", In Proc. 25o Simposio Europeo Anual sobre Algoritmos (ESA) , LIPIcs, 87 : 42: 1–42: 13, doi : 10.4230 / LIPIcs.ESA.2017.42
- Baran, Ilya; Demaine, Erik D .; Pătraşcu, Mihai (2008), "Algoritmos subcuadráticos para 3SUM" , Algorithmica , 50 (4): 584–596, doi : 10.1007 / s00453-007-9036-3.
- Demaine, Erik D .; Mitchell, Joseph SB ; O'Rourke, Joseph (julio de 2005), "Problema 11: 3SUM duro de problemas" , El Proyecto problemas abiertos , Archivado desde el original en 12/15/2012 , recuperada 2008-09-02.
- Erickson, Jeff (1999), "Límites inferiores para problemas de satisfacibilidad lineal" , Chicago Journal of Theoretical Computer Science , MIT Press, 1999.
- Gajentaan, Anka; Overmars, Mark H. (1995), "Sobre una clase de problemas O ( n 2 ) en geometría computacional", Geometría computacional: teoría y aplicaciones , 5 (3): 165-185, doi : 10.1016 / 0925-7721 (95 ) 00022-2 , hdl : 1874/17058.
- King, James (2004), Una encuesta de problemas difíciles de 3SUM (PDF).