Membandingkan Dua Algoritma untuk masalah 3SUM di atas Integer

Makalah "Algoritma Subquadratic for 3SUM", oleh Ilya Baran, Erik D. Demaine, Mihai Patrascu memiliki kompleksitas berikut untuk

Masalah 3SUM: diberi daftar $L$ dari $n$ bilangan bulat jika ada $x,y,z \in L$ sedemikian rupa sehingga $x+y=z.$

$w-$A C 0 O ( n 2 / w 2 log w ) O ( n 2 / ( M B ) ) O ( n 2 / M B log M $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 )$

Baru-baru ini, sebuah makalah "Segitiga Threesomes, Degenerates, dan Love" oleh Grondlund dan Pettie telah membuktikan bahwa "kompleksitas pohon keputusan 3SUM adalah , dan bahwa ada algoritma 3SUM acak yang berjalan dalam waktu , dan algoritma deterministik berjalan dalam O (n ^ 2 (\ log \ log n) ^ {5/3 } / (\ log n) ^ {2/3})O(n2(loglogn)2/logn)O(n2(loglogn) 5 / 3 /(logn) 2 / 3$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})$ waktu.

Hasil ini membantah versi terkuat dari dugaan 3SUM, yaitu bahwa pohon keputusan (dan algoritmik) kompleksitasnya adalah $Ω(n^2)$ . "

Lihat makalah kedua ini di sini .

Jelas, keduanya adalah makalah penting. Tidak menjadi ahli dalam bidang ini, pertanyaan saya adalah tentang bagaimana membandingkan dampak dan signifikansi dari keduanya, mengingat model kompleksitas yang berbeda. Setiap komentar berwawasan lainnya tentang masalah ini juga diterima. Misalnya apakah kertas pertama sudah mengesampingkan batas ?$\Omega(n^2)$

Berikut adalah beberapa poin yang membantu memberikan perspektif pada hasil baru.

Hasil kompleksitas pohon keputusan adalah besar. Satu garis serangan (dan Jeff Erickson dapat mengatakan lebih banyak tentang ini) adalah untuk mencoba dan menurunkan 3SUM melalui melihat kompleksitas keputusan masalah (yaitu jumlah perbandingan yang diperlukan untuk menyelesaikan masalah). Harapannya adalah sesuatu yang dekat dengan dapat dicapai.$\Omega(n^2)$

Hasil ini secara meyakinkan membuang argumen itu dengan ikatan . Perhatikan bahwa ini tidak mengatakan apa pun tentang kompleksitas sebenarnya dari masalah tersebut. Dikatakan bahwa pohon keputusan batas bawah tidak akan terjadi. Dan itu (bersama dengan bukti lain) menimbulkan keraguan pada premis dasar bahwa 3SUM "secara moral" dekat dengan .n $O(n^{3/2})$$n^2$

Hasil algoritmik bersifat subquadratic tanpa syarat (yaitu tidak dalam model kata-paralel). Itu masalah besar, walaupun saya kira orang mungkin berdalih tentang fakta bahwa itu bukan untuk beberapa konstanta$O(n^{2-\epsilon})$$\epsilon$ .

Seperti kata @domotorp, ini bisa menjadi awal dari serangkaian hasil baru. Sangat sulit untuk dikatakan. Batas atas saat ini berasal dari "penerapan kembali" algoritma pohon keputusan dengan beberapa trik sulap dari Timothy Chan. Bisa dibayangkan bahwa ini bisa didorong lebih jauh.

Makalah pertama pada dasarnya memberikan algoritma subquadratic jika kita tahu bahwa setiap nomor input memiliki bit dan kita dapat menambahkan dua nomor bit dalam satu langkah. Ini bukan hasil yang sangat mengejutkan dan tidak mengesampingkan batas .$w$$w$$\Omega(n^2)$

Makalah kedua tidak menggunakan asumsi seperti itu dan meningkatkan eksponen untuk pohon keputusan, yang merupakan kejutan, meskipun tidak sebesar seperti yang akan terjadi pada semua algoritma, yang hanya sedikit meningkat (sehingga menyangkal dugaan terkuat) . Saya kira hasil yang lebih banyak akan segera menyusul.$n$