Сравнение двух алгоритмов для задачи 3SUM над целыми числами

17

Работа «Субквадратичные алгоритмы для 3SUM» Илья Баран, Эрик Д. Демейн, Михай Патраску имеет следующую сложность для

Задача 3SUM: дать список $L$ из $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 )$

Недавно в статье Грондлунда и Петти "Тройки, вырожденные и любовные треугольники" доказано, что "сложность дерева решений 3SUM равна $O(n^{3/2}\sqrt{\log n})$ , и что существует рандомизированный алгоритм 3SUM, работающий за $O(n^2(\log \log n)^2/\log n)$ , и детерминированный алгоритм, работающий за $O(n^2(\log \log n)^{5/3}/(\log n)^{2/3})$ время.

Эти результаты опровергают самую сильную версию гипотезы 3SUM, а именно, что ее дерево решений (и алгоритмическая) сложность $Ω(n^2)$ ».

Смотрите эту вторую статью здесь .

Очевидно, что оба являются важными документами. Не будучи экспертом в этой области, мой вопрос о том, как сравнить воздействие и значимость того или иного, учитывая различные модели сложности. Любые другие проницательные комментарии по этой проблеме также приветствуются. Например, была ли первая статья уже исключена оценка $\Omega(n^2)$ ?

cc.complexity-theory ds.algorithms kodlu
источник

14

Вот некоторые моменты, которые помогают дать представление о новых результатах.

Результат сложности дерева решений большой. Одна из линий атаки (и Джефф Эриксон может сказать больше об этом) состояла в том, чтобы попытаться опустить 3SUM с помощью оценки сложности решения проблемы (т. Е. Количества сравнений, необходимых для решения проблемы). Была надежда, что что-то близкое к было достижимо. $\Omega(n^2)$

Этот результат решительно разрушает этот аргумент с границей . Обратите внимание, что это ничего не говорит об истинной сложности проблемы. Это говорит о том, что нижней границы дерева решений не произойдет. И это (наряду с другими доказательствами) ставит под сомнение основную предпосылку, что 3SUM "морально" близка к . $O(n^{3/2})$ $n^2$

Алгоритмический результат является субквадратичным безоговорочно (то есть не в параллельной модели). Это большое дело, хотя я полагаю, что можно поспорить о том, что это не для некоторой константы . $O(n^{2-\epsilon})$ $\epsilon$

Как говорит @domotorp, это может стать началом ряда новых результатов. Это действительно сложно сказать. Текущая верхняя граница получается из-за «повторной реализации» алгоритма дерева решений с некоторыми волшебными трюками от Тимоти Чана. Вполне возможно, что это может быть продвинуто дальше.

Суреш Венкат
источник

4

Джефф Эриксон может сказать больше об этом - Не намного, чтобы сказать, правда. Я доказал, что естественная модель дерева решений требует глубины ; новая статья показывает, что для очень слабой модели достаточно глубины . В ретросекте этот результат не должен удивлять в свете результатов Фредмана и Чана о сортировке X + Y и кратчайших путях. Но это полностью перекрывает естественную линию атаки. Как я сказал Сету, я одновременно невероятно рад и невероятно ревнив.

Ω (n^{2})

$\Omega(n^2)$

O (n^{3 / 2})

$O(n^{3/2})$

Джефф

14

Первая статья по существу дает субквадратичный алгоритм, если мы знаем, что у каждого входного числа есть битов, и мы можем добавить два числа битов за один шаг. Это был не очень удивительный результат, и он не исключал границы . $w$ $w$ $\Omega(n^2)$

Вторая статья не использует никаких таких предположений и улучшает показатель для деревьев решений, что является неожиданностью, хотя и не таким большим, как было бы для всех алгоритмов, для которых они только немного улучшились (таким образом опровергая самую сильную гипотезу) , Я предполагаю, что в скором времени появятся новые результаты. $n$

domotorp
источник

Я доволен обоими ответами, но мог принять только один, поэтому я принял более подробный.

Кодлу

Сравнение двух алгоритмов для задачи 3SUM над целыми числами

Ответы: