Comparando dois algoritmos para o problema 3SUM sobre números inteiros

O artigo "Algoritmos subquadráticos para 3SUM", de Ilya Baran, Erik D. Demaine, Mihai Patrascu, apresenta a seguinte complexidade para a

Problema 3SUM: dada uma lista $L$ de $n$ números inteiros se houver $x,y,z \in L$ tal que $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 )$

Recentemente, um artigo "Threesomes, Degenerates, and Triangles Love" de Grondlund e Pettie provou que "a complexidade da árvore de decisão de 3SUM é , e que existe um algoritmo 3SUM aleatório executando no tempo e um algoritmo determinístico executando no tempo hora.$O(n^{3/2}\sqrt{\log n})$$O(n^2(\log \log n)^2/\log n)$$O(n^2(\log \log n)^{5/3}/(\log n)^{2/3})$

Esses resultados refutam a versão mais forte da conjectura 3SUM, a saber, que a complexidade da árvore de decisão (e algorítmica) é . "$Ω(n^2)$

Veja este segundo artigo aqui .

Claramente, ambos são documentos importantes. Não sendo especialista nessa área, minha pergunta é sobre como comparar o impacto e a significância de qualquer uma delas, dados os diferentes modelos de complexidade. Quaisquer outros comentários perspicazes sobre esse problema também são bem-vindos. Por exemplo, o primeiro artigo já descartou o limite de ?$\Omega(n^2)$

Aqui estão alguns pontos que ajudam a dar perspectiva aos novos resultados.

O resultado da complexidade da árvore de decisão é grande. Uma linha de ataque (e Jeff Erickson pode dizer mais sobre isso) foi tentar diminuir o limite do 3SUM observando a complexidade da decisão do problema (ou seja, o número de comparações necessárias para solucionar o problema). A esperança era que algo próximo a fosse atingível.$\Omega(n^2)$

Esse resultado descarta decisivamente esse argumento com um limite de . Observe que isso não diz nada sobre a verdadeira complexidade do problema. Diz que um limite inferior da árvore de decisão não vai acontecer. E que (juntamente com outras evidências) põe em dúvida a premissa básica de que 3SUM é "moralmente" próximo de .$O(n^{3/2})$$n^2$

O resultado algorítmico é subquadrático incondicionalmente (ou seja, não em um modelo paralelo à palavra). Isso é muito importante, embora eu suponha que alguém possa reclamar do fato de que não é para um constante .$O(n^{2-\epsilon})$$\epsilon$

Como @domotorp diz, isso pode muito bem ser o começo de uma série de novos resultados. É realmente difícil de dizer. O limite superior atual vem da "reimplementação" do algoritmo da árvore de decisão com alguns truques de mágica de Timothy Chan. É concebível que isso possa ser levado adiante.

O primeiro artigo fornece essencialmente um algoritmo subquadrático se soubermos que todo número de entrada possui bits e podemos adicionar dois números bits em uma etapa. Este não foi um resultado muito surpreendente e não descartou um limite .$w$$w$$\Omega(n^2)$

O segundo artigo não usa essas premissas e melhora o expoente de para árvores de decisão, o que é uma surpresa, embora não seja tão grande quanto seria para todos os algoritmos, para os quais eles apenas melhoraram um pouco (desmentindo a conjectura mais forte) . Eu acho que mais resultados virão em breve.$n$