3SUMA

Problema en la teoría de la complejidad computacional

Problema sin resolver en informática :

¿Existe un algoritmo para resolver el problema 3SUM a tiempo , para algunos ? ${\displaystyle O(n^{2-\epsilon })}$ ${\displaystyle \epsilon >0}$

(más problemas sin resolver en informática)

En la teoría de la complejidad computacional , el problema 3SUM pregunta si un conjunto dado de números reales contiene tres elementos cuya suma es cero. Una versión generalizada, k -SUM, plantea la misma pregunta sobre k elementos, en lugar de simplemente sobre 3. 3SUM se puede resolver fácilmente en el tiempo, y se conocen límites inferiores coincidentes en algunos modelos especializados de computación (Erickson 1999). ${\displaystyle n}$ ${\displaystyle O(n^{2})}$ ${\displaystyle \Omega (n^{\lceil k/2\rceil })}$

Se ha conjeturado que cualquier algoritmo determinista para 3SUM requiere tiempo. En 2014, la conjetura original de 3SUM fue refutada por Allan Grønlund y Seth Pettie, quienes dieron un algoritmo determinista que resuelve 3SUM en el tiempo. ^[1] Además, Grønlund y Pettie demostraron que la complejidad del árbol de decisión lineal 4- de 3SUM es . Estos límites se mejoraron posteriormente. ^{[2] [3] [4]} El algoritmo más conocido actualmente para 3SUM se ejecuta en el tiempo. ^[4] Kane, Lovett y Moran demostraron que la complejidad del árbol de decisión lineal 6- de 3SUM es . ^[5] El último límite es estricto (hasta un factor logarítmico). Todavía se conjetura que 3SUM es irresoluble en el tiempo esperado. ^[6] ${\displaystyle \Omega (n^{2})}$ ${\displaystyle O(n^{2}/({\log n}/{\log \log n})^{2/3})}$ ${\displaystyle O(n^{3/2}{\sqrt {\log n}})}$ ${\displaystyle O(n^{2}(\log \log n)^{O(1)}/{\log ^{2}n})}$ ${\displaystyle O(n{\log ^{2}n})}$ ${\displaystyle O(n^{2-\Omega (1)})}$

Cuando los elementos son números enteros en el rango , 3SUM se puede resolver en el tiempo representando el conjunto de entrada como un vector de bits , calculando el conjunto de todas las sumas por pares como una convolución discreta utilizando la transformada rápida de Fourier y, finalmente, comparando este conjunto con . ^[7] ${\displaystyle [-N,\dots ,N]}$ ${\displaystyle O(n+N\log N)}$ ${\displaystyle S}$ ${\displaystyle S+S}$ ${\displaystyle S}$

Algoritmo cuadrático

Supongamos que la matriz de entrada es . En los modelos de computación de números enteros ( Word RAM ), 3SUM se puede resolver en el tiempo promedio insertando cada número en una tabla hash y luego, para cada índice y , verificando si la tabla hash contiene el número entero . ${\displaystyle S[0..n-1]}$ ${\displaystyle O(n^{2})}$ ${\displaystyle S[i]}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle -(S[i]+S[j])}$

También es posible resolver el problema al mismo tiempo en un modelo de computación basado en comparación o en 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 una búsqueda binaria de los pares en la lista ordenada, logrando el peor tiempo posible, como se muestra a continuación. ^[8] ${\displaystyle O(n^{2})}$

sort(S); para i = 0 a n - 2 hacer a = S[i]; inicio = i + 1; fin = n - 1; mientras (inicio < fin) hacer b = S[inicio] c = S[fin]; si (a + b + c == 0) entonces  salida a, b, c; // Continuar la búsqueda de todas las combinaciones de tripletes cuya suma sea cero. // Necesitamos actualizar tanto el final como el inicio juntos ya que los valores de la matriz son distintos. inicio = inicio + 1; fin = fin - 1; de lo contrario  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 a 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-324810 ( a + b+c==- 7 ) -25-10-7-324810 ( 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-324810 ( a + b + c ==0)

La exactitud del algoritmo se puede comprobar de la siguiente manera. Supongamos que tenemos una solución a + b + c = 0. Como los punteros solo se mueven en una dirección, podemos ejecutar el algoritmo hasta que el puntero situado más a la izquierda apunte a a. Ejecutamos el algoritmo hasta que uno de los punteros restantes apunte a b o c, lo que ocurra primero. Luego, el algoritmo se ejecutará hasta que el último puntero apunte al término restante, lo que dará como resultado 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. La forma más sencilla sería modificar el algoritmo original para buscar en la tabla hash el entero ⁠ ⁠ ${\displaystyle (C-(S[i]+S[j]))}$ .

Otro método:

• Restar C /3 de todos los elementos de la matriz de entrada.
• En la matriz modificada, encuentre 3 elementos cuya suma sea 0.

Por ejemplo, si A = [1,2,3,4] y se le pide encontrar 3SUM para C = 4, entonces reste 4/3 de todos los elementos de A y resuélvalo de la manera habitual de 3sum, es decir, ⁠ ⁠ ${\displaystyle (a-C/3)+(b-C/3)+(c-C/3)=0}$ .

Tres matrices diferentes

En lugar de buscar los 3 números en una única matriz, podemos buscarlos en 3 matrices diferentes. Es decir, dadas tres matrices X, Y y Z, encontramos tres números a ∈ X , b ∈ Y , c ∈ Z , tales que ⁠ ⁠ ${\displaystyle a+b+c=0}$ . Llamamos 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: ⁠ ⁠ ${\displaystyle X[i]\gets X[i]*10+1}$ , ⁠ ⁠ ${\displaystyle Y[i]\gets Y[i]*10+2}$ , ⁠ ⁠ ${\displaystyle Z[i]\gets Z[i]*10-3}$ .
• Sea S una concatenación de las matrices X , Y y Z.
• Utilice el oráculo 3SUM×1 para encontrar tres elementos ⁠ ⁠ ${\displaystyle a'\in S,\ b'\in S,\ c'\in S}$ tales que ⁠ ⁠ ${\displaystyle a'+b'+c'=0}$ .
• Regresar ⁠ ⁠ ${\displaystyle a\gets (a'-1)/10,\ b\gets (b'-2)/10,\ c\gets (c'+3)/10}$ .

Por la forma en que transformamos las matrices, se garantiza que a ∈ X , b ∈ Y , c ∈ Z . ^[9]

Suma de convolución

En lugar de buscar elementos arbitrarios de la matriz tales que:

${\displaystyle S[k]=S[i]+S[j]}$

El problema de convolución 3sum (Conv3SUM) busca elementos en ubicaciones específicas: ^[10]

${\displaystyle S[i+j]=S[i]+S[j]}$

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 en la matriz y los índices van de 0 a n -1). ${\displaystyle T[i]=2nS[i]+i}$
• Resuelva 3SUM en la matriz T.

Prueba de corrección:

• Si en la matriz original hay una tripleta con , entonces , por lo que esta solución se encontrará mediante 3SUM en T . ${\displaystyle S[i+j]=S[i]+S[j]}$ ${\displaystyle T[i+j]=2nS[i+j]+i+j=(2nS[i]+i)+(2nS[j]+j)=T[i]+T[j]}$
• Por el contrario, si en la nueva matriz hay una tripleta con , entonces . Porque , necesariamente y , por lo que esta es una solución válida para Conv3SUM en S . ${\displaystyle T[k]=T[i]+T[j]}$ ${\displaystyle 2nS[k]+k=2n(S[i]+S[j])+(i+j)}$ ${\displaystyle i+j<2n}$ ${\displaystyle S[k]=S[i]+S[j]}$ ${\displaystyle k=i+j}$

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, supongamos que tenemos una función hash lineal, es decir, una función h tal que:

${\displaystyle h(x+y)=h(x)+h(y)}$

Supongamos 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. Crea una nueva matriz T y envía cada elemento de S a su valor hash en T , es decir, para cada x en S ( ⁠ ⁠ ${\displaystyle \forall x\in S}$ ):

${\displaystyle T[h(x)]=x}$

Inicialmente, supongamos que las asignaciones son únicas (es decir, cada celda en T acepta solo un único elemento de S ). Resuelva Conv3SUM en T. Ahora:

• Si hay una solución para 3SUM: , entonces: y , por lo que el solucionador Conv3SUM encontrará esta solución en T . ${\displaystyle z=x+y}$ ${\displaystyle T[h(z)]=T[h(x)]+T[h(y)]}$ ${\displaystyle h(z)=h(x)+h(y)}$
• Por el contrario, si se encuentra una Conv3SUM en T , entonces obviamente corresponde a una solución 3SUM en S ya que T es solo una permutación de S.

Esta solución idealizada no funciona, porque cualquier función hash podría mapear varios elementos distintos de S a la misma celda de T . El truco es crear una matriz ⁠ ⁠ ${\displaystyle T^{*}}$ seleccionando un solo elemento aleatorio de cada celda de T , y ejecutar Conv3SUM en ⁠ ⁠ ${\displaystyle T^{*}}$ . Si se encuentra una solución, entonces es una solución correcta para 3SUM en S . Si no se encuentra ninguna solución, entonces cree una ⁠ ⁠ ${\displaystyle T^{*}}$ aleatoria diferente e intente nuevamente. Suponga que hay como máximo 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 . Al ejecutar Conv3SUM veces, la solución se encontrará con una alta probabilidad. ${\displaystyle (1/R)^{3}}$ ${\displaystyle R^{3}}$

Desafortunadamente, no tenemos un hash lineal perfecto, por lo que tenemos que utilizar una función hash casi lineal, es decir, una función h tal que:

${\displaystyle h(x+y)=h(x)+h(y)}$o

${\displaystyle h(x+y)=h(x)+h(y)+1}$

Esto requiere duplicar los elementos de S al copiarlos en T , es decir, poner cada elemento tanto en (como antes) como en . Por lo tanto, cada celda tendrá 2 elementos R y tendremos que ejecutar Conv3SUM veces. ${\displaystyle x\in S}$ ${\displaystyle T[h(x)]}$ ${\displaystyle T[h(x)]-1}$ ${\displaystyle (2R)^{3}}$

Dureza 3SUM

Un problema se denomina 3SUM-hard si su resolución en tiempo subcuadrático implica un algoritmo de tiempo subcuadrático para 3SUM. El concepto de 3SUM-hard fue introducido por Gajentaan y Overmars (1995). Demostraron que una gran clase de problemas en geometría computacional son 3SUM-hard, incluidos los siguientes. (Los autores reconocen que muchos de estos problemas son contribuciones de otros investigadores.)

• Dado un conjunto de rectas en el plano, ¿hay tres que se encuentran en un punto?
• Dado un conjunto de segmentos de línea paralelos al eje que no se intersecan, ¿existe una línea que los separe en dos subconjuntos no vacíos?
• Dado un conjunto de tiras infinitas en el plano, ¿cubren completamente un rectángulo dado?
• Dado un conjunto de triángulos en el plano, calcule su medida.
• Dado un conjunto de triángulos en el plano, ¿su unión tiene un agujero?
• Una serie de problemas de visibilidad y planificación del movimiento, por ejemplo:
  • Dado un conjunto de triángulos horizontales en el espacio, ¿puede verse un triángulo particular desde un punto particular?
  • Dado un conjunto de obstáculos de segmentos de línea paralelos a ejes que no se intersecan en el plano, ¿puede una varilla dada moverse mediante traslaciones y rotaciones entre una posición inicial y una final sin chocar con los obstáculos?

Actualmente, hay una multitud de otros problemas que caen en esta categoría. Un ejemplo es la versión de decisión de la clasificación X + Y : dados conjuntos de números X e Y de n elementos cada uno, ¿existen n ² x + y distintos para x ∈ X , y ∈ Y ? ^[11]

Véase también

• Problema de suma de subconjuntos

Notas

1. Grønlund y Pettie 2014.
2. Freund 2017.
3. Oro y Sharir 2017.
4. Chan 2018.
5. Kane, Lovett y Moran 2018.
6. Kopelowitz, Tsvi; Pettie, Seth; Porat, Ely (2014). "Dureza 3SUM en estructuras de datos (dinámicas)". arXiv : 1407.6756 [cs.DS].
7. 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.Ejemplo 30.1–7, pág. 906.
8. Gráficos de visibilidad y suma de 3 por Michael Hoffmann
9. Para una reducción en la otra dirección, consulte Variantes del problema de 3 sumas.
10. Patrascu, M. (2010). Hacia límites inferiores polinomiales para problemas dinámicos . Actas del 42.º simposio de la ACM sobre teoría de la computación - STOC '10. pág. 603. doi :10.1145/1806689.1806772. ISBN 9781450300506.
11. Demaine, Erik ; Erickson, Jeff; O'Rourke, Joseph (20 de agosto de 2006). "Problema 41: Ordenar X + Y (sumas por pares)". The Open Problems Project . Consultado el 23 de septiembre de 2014 .

Referencias

• Kane, Daniel M.; Lovett, Shachar; Moran, Shay (2018). "Árboles de decisión lineales casi óptimos para k-SUM y problemas relacionados". Actas del 50.º Simposio anual ACM SIGACT sobre teoría de la computación . págs. 554–563. arXiv : 1705.01720 . doi :10.1145/3188745.3188770. ISBN . 9781450355599.S2CID30368541  .​
• Chan, Timothy M. (2018), "Más aceleraciones de factores logarítmicos para 3SUM, (Median,+)-Convolution y algunos problemas geométricos 3SUM-Hard", Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos , págs. 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. pág. 621. arXiv : 1404.0799 . Bibcode :2014arXiv1404.0799G. doi :10.1109/FOCS.2014.72. ISBN . 978-1-4799-6517-5.
• Freund, Ari (2017), "3SUM subcuadrático mejorado", Algorithmica , 44 (2): 440–458, doi :10.1007/s00453-015-0079-6, S2CID  253979651.
• Gold, Omer; Sharir, Micha (2017), "Límites mejorados para 3SUM, k -SUM y degeneración lineal", en Proc. 25.° Simposio europeo anual sobre algoritmos (ESA) , LIPIcs, 87 : 42:1–42:13, doi : 10.4230/LIPIcs.ESA.2017.42 , S2CID  691387
• 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, S2CID  9855995.
• Demaine, Erik D .; Mitchell, Joseph SB ; O'Rourke, Joseph (julio de 2005), "Problema 11: Problemas difíciles de 3SUM", The Open Problems Project, archivado desde el original el 15 de diciembre de 2012 , consultado el 2 de septiembre de 2008.
• Erickson, Jeff (1999), "Límites inferiores para problemas de satisfacibilidad lineal", Chicago Journal of Theoretical Computer Science , 1999 , MIT Press.
• Gajentaan, Anka; Overmars, Mark H. (1995), "Sobre una clase de problemas O( n ² ) en geometría computacional", Computational Geometry: Theory and Applications , 5 (3): 165–185, doi :10.1016/0925-7721(95)00022-2, hdl : 1874/17058.
• King, James (2004), Un estudio de problemas complejos de 3SUM (PDF).