Porównanie dwóch algorytmów dla problemu 3SUM w stosunku do liczb całkowitych

Artykuł „Algorytmy subkwadratowe dla 3SUM” autorstwa Ilyi Baran, Erika D. Demaine'a, Mihai Patrascu ma następującą złożoność

3SUM problemów: otrzymuje listę $L$ z liczb całkowitych czy istnieją taki sposób, że$n$$x,y,z \in L$$x+y=z.$

Twierdzą oni, „W przypadku standardowego tekstu z pamięci RAM bitowych słów, otrzymujemy czas pracy . W układzie pamięci RAM z jednym niestandardowych operacji otrzymujemy o (n ^ 2 / W ^ 2 \ log W) . W pamięci zewnętrznej, to osiągnąć o (n ^ 2 / (Mb)) , nawet w ramach standardu założenie niepodzielności danych. Nieświadomie cache, otrzymujemy czas działania O (n ^ 2 / MB \ log M) . We wszystkich przypadkach nasze przyspieszenie jest prawie kwadratowe w „równoległości” modelu, który może wykonać, co może być najlepsze możliwe. Zobacz artykuł Barana, Demaine, Patrascu tutaj .O ( n 2 / max { w log w , log n ( log log n ) 2 } ) A C 0 O ( n 2 / w 2 log w ) O ( n 2 / ( M B ) ) O ( n 2 / M B log M $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 )$

Niedawno praca Grondlunda i Pettie „Trójkąty, zwyrodnienia i trójkąty miłosne” dowiodła, że ​​„złożoność drzewa decyzyjnego 3SUM to $O(n^{3/2}\sqrt{\log n})$ i że istnieje losowy algorytm 3SUM działający w czasie $O(n^2(\log \log n)^2/\log n)$ oraz algorytm deterministyczny działający w $O(n^2(\log \log n)^{5/3}/(\log n)^{2/3})$ czas.

Wyniki te obalają najsilniejszą wersję hipotezy 3SUM, a mianowicie, że jej złożoność drzewa decyzyjnego (i algorytmu) wynosi $Ω(n^2)$ . ”

Zobacz ten drugi artykuł tutaj .

Oczywiście oba są ważnymi dokumentami. Nie będąc ekspertem w tej dziedzinie, moje pytanie dotyczy tego, jak porównać wpływ i znaczenie każdego z nich, biorąc pod uwagę różne modele złożoności. Wszelkie inne wnikliwe komentarze na temat tego problemu są również mile widziane. Na przykład, czy pierwszy artykuł wykluczył już ograniczenie $\Omega(n^2)$ ?

Oto kilka punktów, które pomagają spojrzeć na nowe wyniki.

Wynik złożoności drzewa decyzyjnego jest duży. Jedną z linii ataku (i Jeff Erickson może powiedzieć więcej na ten temat) było próba obniżenia 3SUM poprzez spojrzenie na złożoność decyzyjną problemu (tj. Liczbę porównań potrzebnych do rozwiązania problemu). Mieliśmy nadzieję, że coś bliskiego do możliwe do osiągnięcia.$\Omega(n^2)$

Ten wynik zdecydowanie odrzuca ten argument z ograniczeniem . Zauważ, że nie mówi to nic o prawdziwej złożoności problemu. Mówi, że dolna granica drzewa decyzyjnego się nie wydarzy. I to (wraz z innymi dowodami) podważa podstawową przesłankę, że 3SUM jest „moralnie” bliski .$O(n^{3/2})$$n^2$

Wynik algorytmu jest bezwzględnie subkwadratowy (tj. Nie w modelu równoległym do słowa). To wielka sprawa, chociaż przypuszczam, że można się spierać, że nie jest to dla jakiegoś stałego .$O(n^{2-\epsilon})$$\epsilon$

Jak mówi @domotorp, może to być początek serii nowych wyników. Naprawdę trudno powiedzieć. Obecna górna granica pochodzi z „ponownego wdrożenia” algorytmu drzewa decyzyjnego za pomocą magicznych sztuczek Timothy Chana. Można sobie wyobrazić, że można to zrobić dalej.

Pierwszy papier zasadniczo daje algorytm subquadratic jeśli wiemy, że każda liczba ma wejście bitach i możemy dodać dwa liczbie bitów w jednym kroku. Nie był to bardzo zaskakujący wynik i nie wykluczył ograniczenia .$w$$w$$\Omega(n^2)$

Druga praca nie wykorzystuje takich założeń i poprawia wykładnik dla drzew decyzyjnych, co jest zaskoczeniem, choć nie tak dużym, jak by to było w przypadku wszystkich algorytmów, dla których poprawiły się tylko nieznacznie (tym samym odrzucając najsilniejszą hipotezę) . Sądzę, że wkrótce więcej wyników.$n$