Comparación de dos algoritmos para el problema 3SUM sobre enteros

El artículo "Algoritmos subcuadráticos para 3SUM", de Ilya Baran, Erik D. Demaine, Mihai Patrascu tiene la siguiente complejidad para el

Problema 3SUM: dada una lista $L$ de enteros si hay tal quex , y , z ∈ L x + y = z $n$$x,y,z \in L$$x+y=z.$

$w-$$O(n^2/ \max\{w \log w, \log n (\log \log n)^2 \})$$AC0$$O(n^2/ w^2 \log w)$$O(n^2/(MB))$$O(n^2/ MB \log M )$

Recientemente, un documento "Tríos, degenerados y triángulos amorosos" de Grondlund y Pettie ha demostrado que "la complejidad del árbol de decisión de 3SUM es $O(n^{3/2}\sqrt{\log n})$ , y que existe un algoritmo aleatorio de 3SUM que se ejecuta en tiempo $O(n^2(\log \log n)^2/\log n)$ , y un algoritmo determinista que se ejecuta en $O(n^2(\log \log n)^{5/3}/(\log n)^{2/3})$ tiempo.

Estos resultados refutan la versión más fuerte de la conjetura de 3SUM, a saber, que su árbol de decisión (y algorítmico) la complejidad es $Ω(n^2)$ ".

Vea este segundo artículo aquí .

Claramente, ambos son documentos importantes. Al no ser un experto en esta área, mi pregunta es sobre cómo comparar el impacto y la importancia de cualquiera de ellos, dados los diferentes modelos de complejidad. Cualquier otro comentario perspicaz sobre este problema también es bienvenido. Por ejemplo, ¿el primer artículo ya descartó el límite de $\Omega(n^2)$ ?

Aquí hay algunos puntos que ayudan a dar perspectiva a los nuevos resultados.

El resultado de la complejidad del árbol de decisión es grande. Una línea de ataque (y Jeff Erickson puede decir más sobre esto) fue tratar de reducir el límite 3SUM observando la complejidad de decisión del problema (es decir, el número de comparaciones necesarias para resolver el problema). La esperanza era que algo cercano a fuera alcanzable.$\Omega(n^2)$

Este resultado destruye decisivamente ese argumento con un límite . Tenga en cuenta que esto no dice nada sobre la verdadera complejidad del problema. Dice que un límite inferior del árbol de decisión no va a suceder. Y eso (junto con otras pruebas) arroja dudas sobre la premisa básica de que 3SUM está "moralmente" cerca de .$O(n^{3/2})$$n^2$

El resultado algorítmico es subcuadrático incondicionalmente (es decir, no en un modelo de palabras paralelas). Eso es un gran problema, aunque supongo que uno podría objetar el hecho de que no es para alguna constante .$O(n^{2-\epsilon})$$\epsilon$

Como dice @domotorp, esto podría ser el comienzo de una serie de nuevos resultados. Es realmente difícil de decir. El límite superior actual proviene de "volver a implementar" el algoritmo del árbol de decisión con algunos trucos de magia de Timothy Chan. Es concebible que esto pueda llevarse más lejos.

El primer artículo esencialmente proporciona un algoritmo subcuadrático si sabemos que cada número de entrada tiene bits y podemos agregar dos números de bits en un solo paso. Este no fue un resultado muy sorprendente y no descartó un límite .$w$$w$$\Omega(n^2)$

El segundo artículo no utiliza tales supuestos y mejora el exponente de para los árboles de decisión, lo cual es una sorpresa, aunque no tan grande como lo sería para todos los algoritmos, para los cuales solo han mejorado ligeramente (refutando así la conjetura más fuerte) . Supongo que más resultados seguirán en breve.$n$