3СУММ

Нерешенная задача в информатике :

Существует ли алгоритм, позволяющий вовремя решить задачу 3SUM? $O(n^{2-\epsilon })$, для некоторых $\epsilon >0$?

(еще нерешенные проблемы по информатике)

В теории сложности вычислений задача 3SUM спрашивает, является ли данный набор $n$ действительные числа содержат три элемента, сумма которых равна нулю. Обобщенная версия k -SUM задает тот же вопрос для k элементов, а не просто для 3. 3SUM можно легко решить в $O(n^{2})$ время и соответствие $\Omega (n^{\lceil k/2\rceil })$ нижние границы известны в некоторых специализированных моделях вычислений ( Erickson 1999 ).

Было высказано предположение, что любой детерминированный алгоритм 3SUM требует $\Omega (n^{2})$ время. В 2014 году первоначальная гипотеза 3SUM была опровергнута Алланом Грёнлундом и Сетом Петти, которые предложили детерминированный алгоритм, решающий 3SUM в $O(n^{2}/({\log n}/{\log \log n})^{2/3})$ время. Кроме того, Грёнлунд и Петти показали, что сложность 4- линейного дерева решений 3SUM равна $O(n^{3/2}{\sqrt {\log n}})$. Впоследствии эти границы были улучшены. Самый известный на данный момент алгоритм 3SUM работает $O(n^{2}(\log \log n)^{O(1)}/{\log ^{2}n})$ время. Кейн, Ловетт и Моран показали, что сложность 6- линейного дерева решений 3SUM равна $O(n{\log ^{2}n})$. Последняя граница является точной (с точностью до логарифмического множителя). До сих пор предполагается, что 3SUM неразрешима в $O(n^{2-\Omega (1)})$ ожидаемое время.

Когда элементы являются целыми числами в диапазоне $[-N,\dots ,N]$, 3SUM можно решить в $O(n+N\log N)$ время, представляя входной набор $S$ как битовый вектор , вычисляя набор $S+S$ всех парных сумм в виде дискретной свертки с использованием быстрого преобразования Фурье и, наконец, сравнения этого набора с $S$.

Квадратичный алгоритм

Предположим, что входной массив $S[0..n-1]$. В целочисленных ( словных ОЗУ ) моделях вычислений 3SUM можно решить в $O(n^{2})$ среднее время, вставляя каждое число $S[i]$ в хеш-таблицу , а затем для каждого индекса $i$ и $j$, проверяя, содержит ли хэш-таблица целое число $-(S[i]+S[j])$.

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

sort(S);
for i = 0 to n - 2 do
    a = S[i];
    start = i + 1;
    end = n - 1;
    while (start < end) do
        b = S[start]
        c = S[end];
        if (a + b + c == 0) then
            output a, b, c;
            // Continue search for all triplet combinations summing to zero.
            // We need to update both end and start together since the array values are distinct.
            start = start + 1;
            end = end - 1;
        else if (a + b + c > 0) then
            end = end - 1;
        else
            start = start + 1;
    end
end

В следующем примере показано выполнение этого алгоритма на небольшом отсортированном массиве. Текущие значения a показаны красным, значения b и c — пурпурным.

 -25 -10 -7 -3 2 4 8 10  (a+b+c==-25)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-22)
 . . .
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-3)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==2)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==0)

В корректности алгоритма можно убедиться следующим образом. Предположим, у нас есть решение a + b + c = 0. Поскольку указатели движутся только в одном направлении, мы можем запускать алгоритм до тех пор, пока самый левый указатель не укажет на a. Запускайте алгоритм до тех пор, пока один из оставшихся указателей не укажет на b или c, в зависимости от того, что произойдет раньше. Затем алгоритм будет работать до тех пор, пока последний указатель не укажет на оставшийся член, что даст положительное решение.

Варианты

я ненулевой

можно искать числа, сумма которых равна любой константе C. Вместо поиска чисел, сумма которых равна 0 , Самый простой способ — изменить исходный алгоритм для поиска целого числа в хеш-таблице ⁠ $(C-(S[i]+S[j]))$⁠ .

Другой метод:

• Вычтите C /3 из всех элементов входного массива.
• В измененном массиве найдите 3 элемента, сумма которых равна 0.

Например, если A=[1,2,3,4] и вас просят найти 3SUM для C =4, то вычтите 4/3 из всех элементов A и решите ее обычным способом 3SUM, т.е. , ⁠ $(a-C/3)+(b-C/3)+(c-C/3)=0$⁠ .

Три разных массива

Вместо поиска трех чисел в одном массиве мы можем искать их в трех разных массивах. То есть по трем массивам X, Y и Z найдите три числа a ∈ X , b ∈ Y , c ∈ Z такие, что ⁠ $a+b+c=0$⁠ . Назовите вариант с 1 массивом 3SUM×1 и вариант с 3 массивами 3SUM×3.

Учитывая решатель для 3SUM×1, задачу 3SUM×3 можно решить следующим образом (при условии, что все элементы являются целыми числами):

• Для каждого элемента в X , Y и Z установите: ⁠ $X[i]\gets X[i]*10+1$⁠ , ⁠ $Y[i]\gets Y[i]*10+2$⁠ , ⁠ $Z[i]\gets Z[i]*10-3$⁠ .
• Пусть S объединением массивов X , Y и Z. будет
• Используйте оракул 3SUM×1, чтобы найти три элемента ⁠ $a'\in S,\ b'\in S,\ c'\in S$⁠ такой, что ⁠ $a'+b'+c'=0$⁠ .
• Возврат ⁠ $a\gets (a'-1)/10,\ b\gets (b'-2)/10,\ c\gets (c'+3)/10$⁠ .

как мы преобразовали массивы, гарантируется, что a ∈ X , b ∈ Y , c ∈ Z. Тем самым ,

Сумма свертки

Вместо поиска произвольных элементов массива, таких как:

$S[k]=S[i]+S[j]$

задача свертки 3-х сумм (Conv3SUM) ищет элементы в определенных местах:

$S[i+j]=S[i]+S[j]$

Сокращение с Conv3SUM до 3SUM

Имея решатель для 3SUM, задачу Conv3SUM можно решить следующим образом.

• Определите новый массив T так, чтобы для каждого индекса i : $T[i]=2nS[i]+i$ (где n — количество элементов массива, а индексы — от 0 до n -1).
• Решите 3SUM на массиве T .

Доказательство правильности:

• Если в исходном массиве есть тройка с $S[i+j]=S[i]+S[j]$, затем $T[i+j]=2nS[i+j]+i+j=(2nS[i]+i)+(2nS[j]+j)=T[i]+T[j]$, поэтому это решение будет найдено функцией 3SUM на T .
• И наоборот, если в новом массиве имеется тройка с $T[k]=T[i]+T[j]$, затем $2nS[k]+k=2n(S[i]+S[j])+(i+j)$. Потому что $i+j<2n$, обязательно $S[k]=S[i]+S[j]$ и $k=i+j$, так что это допустимое решение для Conv3SUM на S .

Сокращение с 3SUM до Conv3SUM

Учитывая решатель Conv3SUM, задачу 3SUM можно решить следующим образом.

При сокращении используется хэш-функция . В первом приближении предположим, что у нас есть линейная хэш-функция, то есть функция h такая, что:

$h(x+y)=h(x)+h(y)$

Предположим, что все элементы являются целыми числами в диапазоне: 0... N -1 и что функция h сопоставляет каждый элемент с элементом в меньшем диапазоне индексов: 0... n -1. Создайте новый массив T и отправьте каждому элементу S его хеш-значение в T , то есть для каждого x в S ( ⁠ $\forall x\in S$⁠ ):

$T[h(x)]=x$

Сначала предположим, что отображения уникальны (т.е. каждая ячейка в T принимает только один элемент из S ). Решите Conv3SUM на T . Сейчас:

• Если есть решение для 3SUM: $z=x+y$, затем: $T[h(z)]=T[h(x)]+T[h(y)]$ и $h(z)=h(x)+h(y)$, поэтому это решение будет найдено решателем Conv3SUM на T .
• И наоборот, если Conv3SUM найден на T , то, очевидно, оно соответствует решению 3SUM на S, T — это просто перестановка S. поскольку

Это идеализированное решение не работает, поскольку любая хэш-функция может сопоставить несколько различных элементов S ячейкой T. с одной и той же Хитрость заключается в том, чтобы создать массив ⁠ $T^{*}$⁠ выбрав один случайный элемент из каждой ячейки T и запустив Conv3SUM на ⁠ $T^{*}$⁠ . это правильное решение для 3SUM на S. Если решение найдено, то Если решение не найдено, создайте другой случайный ⁠ $T^{*}$⁠ и повторите попытку. содержится не более R Предположим, что в каждой ячейке T элементов . Тогда вероятность найти решение (если решение существует) — это вероятность того, что случайный выбор выберет правильный элемент из каждой ячейки, то есть $(1/R)^{3}$. Запустив Conv3SUM $R^{3}$ раз решение будет найдено с большой вероятностью.

К сожалению, у нас нет линейного идеального хеширования, поэтому нам приходится использовать почти линейную хэш-функцию , то есть функцию h такую, что:

$h(x+y)=h(x)+h(y)$ или

$h(x+y)=h(x)+h(y)+1$

Для этого необходимо дублировать элементы S при копировании их в T , т. е. помещать каждый элемент $x\in S$ оба в $T[h(x)]$ (как и раньше) и в $T[h(x)]-1$. Таким образом, в каждой ячейке будет 2 элемента R , и нам придется запустить Conv3SUM. $(2R)^{3}$ раз.

3SUM-твердость

Задача называется 3SUM-трудной , если ее решение за субквадратичное время субквадратичного времени предполагает использование алгоритма для 3SUM. Понятие твердости 3SUM было введено Гаджентааном и Овермарсом (1995) . Они доказали, что большой класс задач вычислительной геометрии является 3SUM-сложным, включая следующие. (Авторы признают, что многие из этих проблем созданы другими исследователями.)

• Учитывая набор прямых на плоскости, есть ли три, которые пересекаются в одной точке?
• Учитывая набор непересекающихся отрезков, параллельных осям, существует ли линия, которая разделяет их на два непустых подмножества?
• Учитывая набор бесконечных полос на плоскости, полностью ли они покрывают данный прямоугольник?
• Учитывая набор треугольников на плоскости, вычислите их меру.
• Если задан набор треугольников на плоскости, есть ли в их объединении дырка?
• Ряд проблем с обзорностью и планированием движения, например:
  • Можно ли увидеть в пространстве набор горизонтальных треугольников из определенной точки?
  • Учитывая набор непересекающихся препятствий в виде отрезков прямых, параллельных осям, может ли данный стержень перемещаться путем поступательного перемещения и вращения между начальным и конечным положениями, не сталкиваясь с препятствиями?

К настоящему времени существует множество других проблем, подпадающих под эту категорию. Примером является решающая версия сортировки X + Y : для заданных наборов чисел X и Y, состоящих из n элементов каждый, существует ли n ² различных x + y для x ∈ X , y ∈ Y ?

См. также

• Проблема суммы подмножества

Ссылки

• Кейн, Дэниел М.; Ловетт, Шачар; Моран, Шей (2018). «Почти оптимальные линейные деревья решений для k-SUM и связанных с ними задач». Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений . стр. 554–563. arXiv : 1705.01720 . дои : 10.1145/3188745.3188770 . ISBN  9781450355599 . S2CID   30368541 .
• Чан, Тимоти М. (2018), «Больше ускорений с логарифмическим коэффициентом для 3SUM, (Median,+)-свертки и некоторых геометрических сложных задач 3SUM», Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 881–897, doi : 10.1137/1.9781611975031.57 , ISBN.  978-1-61197-503-1
• Грёнлунд, А.; Петти, С. (2014). Секс втроем, дегенераты и любовные треугольники . 55-й ежегодный симпозиум IEEE по основам информатики, 2014 г. п. 621. arXiv : 1404.0799 . Бибкод : 2014arXiv1404.0799G . дои : 10.1109/FOCS.2014.72 . ISBN  978-1-4799-6517-5 .
• Фрейнд, Ари (2017), «Улучшенная субквадратичная 3SUM», Algorithmica , 44 (2): 440–458, doi : 10.1007/s00453-015-0079-6 , S2CID   253979651 .
• Золото, Омер; Шарир, Миха (2017), «Улучшенные границы для 3SUM, k -SUM и линейного вырождения», В Proc. 25-й ежегодный европейский симпозиум по алгоритмам (ESA) , LIPics, 87 : 42:1–42:13, doi : 10.4230/LIPIcs.ESA.2017.42 , S2CID   691387
• Баран, Илия; Демейн, Эрик Д .; Патрашку, Михай (2008), «Подквадратичные алгоритмы для 3SUM» , Algorithmica , 50 (4): 584–596, doi : 10.1007/s00453-007-9036-3 , S2CID   9855995 .
• Демейн, Эрик Д .; Митчелл, Джозеф С.Б .; О'Рурк, Джозеф (июль 2005 г.), «Задача 11: сложные задачи 3SUM» , The Open Issues Project , заархивировано из оригинала 15 декабря 2012 г. , получено 2 сентября 2008 г.
• Эриксон, Джефф (1999), «Нижние оценки для задач линейной выполнимости» , Чикагский журнал теоретической информатики , 1999 , MIT Press .
• Гаджентаан, Анка; Овермарс, Марк Х. (1995), «Об одном классе O( n ² ) проблемы вычислительной геометрии», Вычислительная геометрия: теория и приложения , 5 (3): 165–185, doi : 10.1016/0925-7721(95)00022-2 , hdl : 1874/17058 .
• Кинг, Джеймс (2004), Обзор сложных задач 3SUM (PDF) .