3СУММА

Нерешенная проблема в информатике :

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

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

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

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

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

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

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

сортировка(S); для i = 0 до n - 2 сделать а = S[i]; начало = я + 1; конец = n - 1; пока (начало < конец) делать б = С[начало] c = S[конец]; если (a + b + c == 0) , то  вывести a, b, c; // Продолжаем поиск всех триплетных комбинаций, дающих в сумме ноль. // Нам нужно обновить и конец, и начало одновременно, поскольку значения массива различны. начало = начало + 1; конец = конец - 1; иначе  если (a + b + c > 0) тогда конец = конец - 1; еще начало = начало + 1; конец конец

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

 -25  -10 -7 -3 2 4 8 10 (а+б+в==-25) -25 -10 -7 -3 2 4 8 10 (а+б+в==-22) . . . -25 -10 -7 -3 2 4 8  10 (а+б+в==-7) -25 -10  -7 -3 2 4 8 10 (а+б+в==-7) -25 -10 -7 -3 2 4 8 10 (а+б+в==-3) -25 -10 -7 -3 2 4 8 10 (а+б+в==2) -25 -10 -7 -3 2 4 8 10 (а+б+в==0)

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

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

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

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

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

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

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

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

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

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

${\displaystyle S[k]=S[i]+S[j]}$

задача свертки 3sum (Conv3SUM) ищет элементы в определенных местах: ^[10]

${\displaystyle S[i+j]=S[i]+S[j]}$

При наличии решателя для 3SUM задачу Conv3SUM можно решить следующим образом. ^[10]

• Определим новый массив T таким образом, чтобы для каждого индекса i : (где n — количество элементов в массиве, а индексы варьируются от 0 до n -1).${\displaystyle T[i]=2nS[i]+i}$
• Решите 3СУММ для массива T.

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

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

При наличии решателя для Conv3SUM задачу 3SUM можно решить следующим образом. ^{[6] [10]}

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

${\displaystyle h(x+y)=h(x)+h(y)}$

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

${\displaystyle T[h(x)]=x}$

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

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

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

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

${\displaystyle h(x+y)=h(x)+h(y)}$или

${\displaystyle h(x+y)=h(x)+h(y)+1}$

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

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

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

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

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

• Кейн, Дэниел М.; Ловетт, Шачар; Моран, Шей (2018). «Почти оптимальные линейные деревья решений для k-SUM и связанных с ними проблем». Труды 50-го ежегодного симпозиума ACM SIGACT по теории вычислений . стр.  554–563 . arXiv : 1705.01720 . doi : 10.1145 /3188745.3188770. ISBN 9781450355599. S2CID  30368541.
• Чан, Тимоти М. (2018), «Больше ускорений логарифмического фактора для 3SUM, (медианой,+)-свертки и некоторых геометрических 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 . Bibcode : 2014arXiv1404.0799G. doi : 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 и линейной вырожденности», в трудах 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.
• Demaine, Erik D. ; Mitchell, Joseph SB ; O'Rourke, Joseph (июль 2005 г.), "Problem 11: 3SUM Hard Problems", The Open Problems Project, архивировано из оригинала 2012-12-15 , извлечено 2008-09-02.
• Эриксон, Джефф (1999), «Нижние границы для задач линейной выполнимости», Чикагский журнал теоретической компьютерной науки , 1999 , MIT Press.
• Gajentaan, Anka; Overmars, Mark H. (1995), "О классе O( n ² ) задач в вычислительной геометрии", Computational Geometry: Theory and Applications , 5 (3): 165– 185, doi : 10.1016/0925-7721(95)00022-2, hdl : 1874/17058.
• Кинг, Джеймс (2004), Обзор 3SUM-трудных задач (PDF).