¿Problema generalizado de 3SUM (k-SUM)?

29

El problema 3SUM intenta identificar 3 enteros de un conjunto S de tamaño n tal que a + b + c = 0 .a,b,cSna+b+c=0

Se conjetura que no hay mejor solución que la cuadrática, es decir, . O para decirlo de otra manera: o ( n log ( n ) + n 2 ) .o(n2)o(nlog(n)+n2)

Entonces me preguntaba si esto se aplicaría al problema generalizado: Encuentre enteros para i [ 1 .. k ] en un conjunto S de tamaño n tal que i [ 1 .. k ] a i = 0 .aii[1..k]Sni[1..k]ai=0

Creo que puede hacer esto en para k 2 (es trivial generalizar el algoritmo simple k = 3 ). ¿Pero hay mejores algoritmos para otros valores de k ?o(nlog(n)+nk1)k2k=3
k

máscara de bits
fuente
noticias recientes / papel sobre 3SUM que mira a cotas inferiores de su complejidad árbol de decisiones
VZN

Respuestas:

27

k -SUM se puede resolver más rápidamente de la siguiente manera.

  • Para incluso k : Calcule una lista ordenada S de todas las sumas de k/2 elementos de entrada. Verifique si S contiene tanto algún número x como su negación x . El algoritmo se ejecuta en tiempo O(nk/2logn) .

  • Para k impar : Calcule la lista ordenada S de todas las sumas de elementos de entrada (k1)/2 . Para cada elemento de entrada a , verifique si S contiene tanto x como ax , para algún número x . (El segundo paso es esencialmente el algoritmo de tiempo O(n2) para 3SUM.) El algoritmo se ejecuta en tiempo O(n(k+1)/2) .

Ambos algoritmos son óptimos (excepto posiblemente para el factor log cuando k es par y mayor que 2 ) para cualquier constante k en una cierta restricción débil pero natural del modelo de cálculo del árbol de decisión lineal. Para más detalles, ver:

JeffE
fuente
stackoverflow.com/a/14737071/511736 sugiere el algoritmo O (n ^ 2) cuando k = 4
Kowser
1
Hashing es hacer trampa. El algoritmo descrito en StackOverflow solo se ejecuta en tiempo O (n ^ 2) para la entrada de enteros, y solo con alta probabilidad, y solo si utiliza una función aleatoria de hash apropiada. Los algoritmos en mi respuesta funcionan en el modelo de RAM real, son completamente deterministas y los límites de tiempo son el peor de los casos. También puede eliminar los factores de registro en la configuración de enteros utilizando "trucos de bits", pero eso es un poco aburrido.
JeffE
12

-SUM requiere tiempo n Ω ( d ) a menos que k-SAT pueda resolverse en 2 o ( n ) tiempo para cualquier constante k. Esto se mostró en unartículode Mihai Patrascu y Ryan Williams (1).dnΩ(d)2o(n)

En otras palabras, suponiendo la hipótesis del tiempo exponencial , su algoritmo es óptimo hasta un factor constante en el exponente (un factor polinómico en )n

(1) Mihai Patrascu y Ryan Williams. Sobre la posibilidad de algoritmos SAT más rápidos. Proc. XXI Simposio ACM / SIAM sobre Algoritmos Discretos (SODA2010)

SamM
fuente
3

Aquí hay algunas observaciones simples.

Para , puede hacerlo en Θ ( n ) tiempo escaneando la matriz en busca de un cero. Para k = 2 , puede hacerlo sin hash en Θ ( n log n ) tiempo. Ordene la matriz y luego escanee. Para cada elemento i hacer una búsqueda binaria para - i . Esto da como resultado una complejidad total de Θ ( n log n ) . Para el caso k = n puedes hacerlo en Θ ( n )k=1Θ(n)k=2Θ(nlogn)iiΘ(nlogn)k=nΘ(n) tiempo acumulando la matriz y verificando el resultado.

Para obtener más referencias, consulte la página del Proyecto de problemas abiertos para 3SUM .

Juho
fuente
-1

Ver http://arxiv.org/abs/1407.4640

Un nuevo algoritmo para resolver el problema de rSUM Valerii Sopin

Abstracto:

Se presenta un algoritmo determinado para resolver el problema de rSUM para cualquier r natural con una evaluación subcuadrática de la complejidad del tiempo en algunos casos. En términos de una cantidad de memoria utilizada, el algoritmo obtenido también tiene un orden subcuadrático. La idea del algoritmo obtenido se basa no considerando números enteros, sino más bien k∈N bits sucesivos de estos números en el sistema de numeración binaria. Se muestra que si una suma de números enteros es igual a cero, entonces la suma de números presentada por cualquier k bits sucesivos de estos números debe estar suficientemente "cerca" de cero. Esto hace posible descartar los números, que a fortiori, no establecen la solución.

Es algo nuevo en este tema.

usuario20970
fuente
1
¿Podría citar explícitamente los resultados del artículo que sean relevantes para la pregunta? (Pegar el resumen puede estar bien, si el artículo es relevante en su conjunto). Se supone que las publicaciones en SE son más que un simple enlace.
FrankW
1
Tal como están las cosas, esta respuesta es un comentario (potencialmente útil), no una respuesta. Como tal, debería contener algún contenido original, por ejemplo, describir el algoritmo en sus propias palabras. Quieres hacer eso? Puedo convertir tu respuesta en un comentario si no lo haces. (Soy consciente de que no puede comentar debido a su representante)
Raphael
Eso no parece un documento creíble. La afirmación "complejidad de tiempo sub-cuadrática en algunos casos" no es una declaración útil. La complejidad del tiempo es, por definición, el peor tiempo de ejecución. La clasificación de burbujas se ejecuta en tiempo lineal en algunos casos, pero su complejidad temporal sigue siendo cuadrática.
DW