El problema 3SUM intenta identificar 3 enteros de un conjunto S de tamaño n tal que a + 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 ) .
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 .
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 ?
complexity-theory
combinatorics
complexity-classes
máscara de bits
fuente
fuente
Respuestas:
Para inclusok : 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 / 2Iniciar sesiónn ) .
Parak impar : Calcule la lista ordenada S de todas las sumas de elementos de entrada ( k - 1 ) / 2 . Para cada elemento de entrada una , verifique si S contiene tanto X como - a - x , 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 cuandok 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:
Nir Ailon y Bernard Chazelle. Límites inferiores para pruebas de degeneración lineal . JACM 2005.
Jeff Erickson. Límites inferiores para problemas de satisfacción lineal . CJTCS 1999.
fuente
-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).re nΩ(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)
fuente
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) i −i Θ(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 .
fuente
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.
fuente