SUMA 3

„3 suma” przekierowuje tutaj. W przypadku napoju słodowego patrz Porównanie alkopopów § Na bazie piwa .

Nierozwiązany problem w informatyce :

$}$ istnieje algorytm rozwiązania problemu 3SUM w czasie dla pewnego czasu O $(n ^ {2- \ epsilon})$ ?

(więcej nierozwiązanych problemów w informatyce)

W teorii złożoności obliczeniowej problem 3SUM pyta $,$ czy dany zbiór trzy elementy, których suma wynosi zero. Uogólniona wersja, k -SUMA, zadaje to samo pytanie na k liczbach. 3SUM można łatwo rozwiązać w czasie i dopasować $n$${\ Displaystyle \ Omega (n ^ {$ dolne granice są znane w niektórych wyspecjalizowanych modelach obliczeniowych ( Erickson 1999 ).

Przypuszczano, że każdy $dla$ . W 2014 roku pierwotna hipoteza 3SUM została obalona przez Allana Grønlunda i Setha Pettie, którzy podali deterministyczny algorytm rozwiązujący 3SUM w ${\ Displaystyle O (n ^{2}/({\log n}/{\log \log n})^{2/3})}$ czas. Dodatkowo Grønlund i Pettie wykazali, że 4- liniowa złożoność drzewa decyzyjnego 3SUMA to ${\ Displaystyle O (n ^ {3/2} {\ sqrt {\ log n}})}$ . Granice te zostały następnie poprawione. Obecnie najbardziej znany algorytm dla 3SUM działa w ${\ Displaystyle O (n ^ {2} (\ log \ log n) ^ {O (1)} / {\ log ^ {2} n})}$ czas. Kane, Lovett i Moran wykazali, że 6- liniowa złożoność drzewa decyzyjnego 3SUM wynosi ${\ Displaystyle O (n {\ log ^ {2} n})}$ . Ta ostatnia granica jest ścisła (do współczynnika logarytmicznego). $_$ się czasie

Gdy elementy są liczbami całkowitymi z zakresu ${\ Displaystyle [-N, \ kropki, N]}$ , 3SUMA można rozwiązać w ${\ Displaystyle O (n + N \ log N)}$ czasu, reprezentując zbiór wejściowy jako wektor bitowy , obliczając zbiór wszystkich sum parami jako dyskretny splot $displaystyle S + S$$}$ używając szybkiej transformaty Fouriera i ostatecznie porównując ten $z$ .

Algorytm kwadratowy

Załóżmy, że tablica wejściowa to ${\ Displaystyle S [0 .. n-1]}$ . W modelach obliczeń całkowitych ( słowo RAM $}$$ja$ można rozwiązać w czasie, wstawiając każdą liczbę $S [$ do tablicy mieszającej , a następnie dla każdego indeksu ${\ displaystyle i}$ i ${\ displaystyle j}$ , sprawdzając, czy tablica skrótów zawiera liczbę całkowitą ${\ Displaystyle - (S [i] + S [j])}$ .

Możliwe jest również rozwiązanie problemu w tym samym czasie w porównawczym modelu obliczeniowym lub rzeczywistej pamięci RAM , dla których haszowanie jest niedozwolone. Poniższy algorytm najpierw sortuje tablicę wejściową, a następnie testuje wszystkie możliwe pary w starannej kolejności, która pozwala uniknąć konieczności wyszukiwania binarnego par na posortowanej liście, osiągając najgorszy przypadek ${\ Displaystyle O (n ^ { 2})}$ czas w następujący sposób.

              sortuj(S);  dla  i = 0  do  n - 2  wykonaj  a = S[i]; początek = i + 1;  koniec = n - 1;   while  (początek < koniec)  do  b = S[początek] c = S[koniec];  jeśli  (a + b + c == 0)  to  wyprowadź  a, b, c; // Kontynuuj wyszukiwanie wszystkich kombinacji trójek sumujących się do zera.  // Musimy zaktualizować zarówno koniec, jak i początek razem, ponieważ wartości tablicy są różne.  początek = początek + 1;  koniec = koniec - 1;   w przeciwnym razie  , jeśli  (a + b + c > 0) 
 następnie  koniec = koniec - 1;  inaczej  start = start + 1;  koniec  koniec 

Poniższy przykład pokazuje wykonanie tego algorytmu na małej posortowanej tablicy. Bieżące wartości a są pokazane na czerwono, wartości b i c są pokazane na purpurowo.

     -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) 

Poprawność algorytmu można zobaczyć w następujący sposób. Załóżmy, że mamy rozwiązanie a + b + c = 0. Ponieważ wskaźniki poruszają się tylko w jednym kierunku, możemy uruchamiać algorytm, aż skrajny lewy wskaźnik wskaże a. Uruchom algorytm, aż jeden z pozostałych wskaźników wskaże b lub c, w zależności od tego, co nastąpi wcześniej. Następnie algorytm będzie działał, aż ostatni wskaźnik wskaże pozostały wyraz, dając rozwiązanie twierdzące.

Warianty

Suma niezerowa

Zamiast szukać liczb, których suma wynosi 0, można szukać liczb, których suma jest dowolną stałą C . Najprostszym sposobem byłoby zmodyfikowanie oryginalnego algorytmu w celu przeszukania tablicy skrótów dla liczby całkowitej ${\ Displaystyle (C- (S [i] + S [j]) )}$ .

Inna metoda:

• Odejmij C /3 od wszystkich elementów tablicy wejściowej.
• W zmodyfikowanej tablicy znajdź 3 elementy, których suma wynosi 0.

Na przykład, jeśli A=[1,2,3,4] i jeśli zostaniesz poproszony o znalezienie SUMA 3 dla C = 4, odejmij 4/3 od wszystkich elementów A i rozwiąż to w zwykły sposób sumowania 3, tj. , ${\ Displaystyle (aC/3) + (bC/3) + (cC/3) = 0}$ .

Trzy różne tablice

Zamiast szukać 3 liczb w jednej tablicy, możemy je wyszukać w 3 różnych tablicach. To znaczy, biorąc pod uwagę trzy tablice X, Y i Z, znajdź trzy liczby za ∈ X , b ∈ Y , do ∈ Z , takie że ${\ Displaystyle a + b + c = 0$ . Nazwij wariant 1-tablicowy 3SUMA×1, a wariant 3-tablicowy 3SUM×3.

Biorąc pod uwagę solver dla 3SUMA×1, problem 3SUMA×3 można rozwiązać w następujący sposób (zakładając, że wszystkie elementy są liczbami całkowitymi):

• Dla każdego elementu w X , Y i Z ustaw: ${\ Displaystyle X [i] \ dostaje X [i] * 10 + 1}$ , ${\ Displaystyle Y [i] \ dostaje Y [i] * 10 + 2}$ , ${\ Displaystyle Z [i] \ dostaje Z [i] * 10-3}$ .
• Niech S będzie konkatenacją tablic X , Y i Z .
• ${\ Displaystyle a'+ b'+ c'=0}$ wyroczni 3SUM × 1, aby znaleźć trzy elementy takie, że ${\ Displaystyle a'\ in S, \ b'\ in S, \ c'\ in S$ .
• Zwróć $\ Displaystyle a \ dostaje (a'-1) / 10, \ b \gets (b'-2)/10,\ c\gets (c'+3)/10}$ .

Przy okazji przekształcając tablice, mamy pewność, że a ∈ X , b ∈ Y , c ∈ Z .

Suma splotu

Zamiast szukać dowolnych elementów tablicy, takich jak:

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

problem splotu 3sum (Conv3SUM) szuka elementów w określonych lokalizacjach:

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

Redukcja z Conv3SUM do 3SUM

Biorąc pod uwagę solver dla 3SUM, problem Conv3SUM można rozwiązać w następujący sposób.

• $_$ nową T każdego indeksu liczbą _ _ _ tablicę, a indeksy biegną od 0 do n -1).
• Rozwiąż 3SUM na tablicy T .

Dowód poprawności:

• Jeśli w oryginalnej tablicy jest potrójna z ${\ Displaystyle S [i + j] = S [i] + S [j]}$ , to ${\ Displaystyle T [i + j] = 2nS [i + j] + i + j = (2nS [i] + i)+(2nS[j]+j)=T[i]+T[j]}$ , więc to rozwiązanie zostanie znalezione przez 3SUM na T .
• I odwrotnie, jeśli w nowej tablicy jest potrójna z ${\ Displaystyle T [k] = T [i] + T [j]}$ , to ${\ Displaystyle 2nS [k] + k = 2n (S [i] + S [j]) + (i + j)}$ . Ponieważ ${\ Displaystyle i + j <2n}$ , koniecznie ${\ Displaystyle S [k] = S [i] + S [j]}$ i ${\ displaystyle k = i + j}$ , więc jest to prawidłowe rozwiązanie dla Conv3SUM na S .

Redukcja z 3SUM do Conv3SUM

Biorąc pod uwagę solver dla Conv3SUM, problem 3SUM można rozwiązać w następujący sposób.

Redukcja wykorzystuje funkcję mieszającą . W pierwszym przybliżeniu załóżmy, że mamy liniową funkcję haszującą, tj. funkcję h taką, że:

${\ Displaystyle h (x + y) = h (x) + h (y)$

Załóżmy, że wszystkie elementy są liczbami całkowitymi z zakresu: 0... N -1 i że funkcja h odwzorowuje każdy element na element z mniejszego zakresu indeksów: 0... n -1. Utwórz nową tablicę T i wyślij każdy element S do jego wartości skrótu w T , tj. Dla każdego x w S ( ${\ displaystyle \ forall x \ in S}$ ):

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

Załóżmy początkowo, że odwzorowania są unikalne (tj. każda komórka w T przyjmuje tylko jeden element z S ). Rozwiąż Conv3SUM na T . Teraz:

• Jeśli istnieje rozwiązanie dla 3SUMY: ${\ Displaystyle z = x + y}$ , to: ${\ styl wyświetlania T[h(z)]=T[h(x)]+T[h(y)]}$ i ${\ Displaystyle h (z) = h (x) + h (y)}$ , więc to rozwiązanie zostanie znalezione przez solver Conv3SUM na T .
• I odwrotnie, jeśli Conv3SUM zostanie znalezione na T , to oczywiście odpowiada rozwiązaniu 3SUM na S , ponieważ T jest tylko permutacją S .

To wyidealizowane rozwiązanie nie działa, ponieważ każda funkcja skrótu może odwzorować kilka różnych elementów S na tę samą komórkę T . Sztuczka polega na utworzeniu tablicy przez wybranie pojedynczego losowego elementu z każdej komórki T i uruchomienie Conv3SUM na $T$$}}$ . Jeśli zostanie znalezione rozwiązanie, jest to poprawne rozwiązanie dla 3SUM na S . Jeśli nie zostanie znalezione żadne rozwiązanie, utwórz inny losowy ${\ Displaystyle T ^ {*}}$ i spróbuj ponownie. Załóżmy, że w każdej komórce T jest co najwyżej R elementów . Wtedy prawdopodobieństwo znalezienia rozwiązania (jeśli rozwiązanie istnieje) jest prawdopodobieństwem, że losowy wybór wybierze właściwy element z każdej komórki, czyli ${\ Displaystyle (1/R) ^ {3}}$ . Uruchamiając razy Conv3SUM $,$ zostanie znalezione z dużym prawdopodobieństwem

Niestety nie mamy liniowego idealnego haszowania, więc musimy użyć prawie liniowej funkcji haszującej, czyli funkcji h takiej, że:

${\ Displaystyle h (x + y) = h (x) + h (y)}$ lub

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

$}$ elementów S podczas kopiowania ich do T , . Umieszczenia każdego elementu zarówno w $]$ (jak poprzednio) iw ${\ Displaystyle T [h (x)] -1}$ . Więc każda komórka będzie miała 2 R i będziemy musieli uruchomić Conv3SUM ${\ Displaystyle (2R) ^ {3}}$ razy.

Twardość 3SUM

Problem nazywa się 3SUM-trudny , jeśli rozwiązanie go w czasie subkwadratowym implikuje algorytm czasu subkwadratowego dla 3SUM. Pojęcie twardości 3SUM zostało wprowadzone przez Gajentaana i Overmarsa (1995) . Udowodnili, że duża klasa problemów w geometrii obliczeniowej jest trudna do 3SUM, w tym następujące. (Autorzy przyznają, że wiele z tych problemów zostało wniesionych przez innych badaczy).

• Biorąc pod uwagę zestaw linii na płaszczyźnie, czy są trzy, które spotykają się w jednym punkcie?
• Czy biorąc pod uwagę zestaw nieprzecinających się odcinków linii równoległych do osi, istnieje linia, która dzieli je na dwa niepuste podzbiory?
• Biorąc pod uwagę zestaw nieskończonych pasków na płaszczyźnie, czy w pełni pokrywają one dany prostokąt?
• Mając dany zbiór trójkątów na płaszczyźnie, oblicz ich miarę.
• Biorąc pod uwagę zestaw trójkątów na płaszczyźnie, czy ich połączenie ma dziurę?
• Szereg problemów z widocznością i planowaniem ruchu, np.
  • Biorąc pod uwagę zestaw poziomych trójkątów w przestrzeni, czy określony trójkąt można zobaczyć z określonego punktu?
  • Biorąc pod uwagę zbiór nie przecinających się osiowo-równoległych odcinków przeszkód w płaszczyźnie, czy dany pręt może być przesuwany przez translacje i obroty między pozycją początkową a końcową bez kolizji z przeszkodami?

Do tej pory istnieje wiele innych problemów, które należą do tej kategorii. Przykładem jest wersja decyzyjna sortowania X + Y : czy przy danych zbiorach liczb X i Y po n elementach każdy jest n ² różnych x + y dla x ∈ X , y ∈ Y ?

Zobacz też

• Problem sumy podzbioru

Notatki

•   Kane, Daniel M.; Lovett, Szachar; Moran, Shay (2018). „Niemal optymalne liniowe drzewa decyzyjne dla k-SUM i powiązanych problemów”. Materiały z 50. dorocznego sympozjum ACM SIGACT na temat teorii informatyki (STOC) : 554–563. ar Xiv : 1705.01720 . doi : 10.1145/3188745.3188770 . ISBN 9781450355599 .
•   Chan, Timothy M. (2018), „More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems”, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA) : 881–897, doi : 10.1137/1.9781611975031.57 , ISBN 978-1-61197-503-1
•   Grønlund, A.; Pettie, S. (2014). Trójkąty, degeneraci i trójkąty miłosne . 2014 IEEE 55. doroczne sympozjum na temat podstaw informatyki. P. 621. ar Xiv : 1404.0799 . Bibcode : 2014arXiv1404.0799G . doi : 10.1109/FOCS.2014.72 . ISBN 978-1-4799-6517-5 .
• Freund, Ari (2017), „Improved Subquadratic 3SUM”, Algorithmica , 44 (2): 440–458, doi : 10.1007/s00453-015-0079-6 .
• złoto, omer; Sharir, Micha (2017), „Improved Bounds for 3SUM, k -SUM and Linear Degeneracy”, In Proc. 25th Annual European Symposium on Algorithms (ESA) , LIPIcs, 87 : 42:1–42:13, doi : 10.4230/LIPIcs.ESA.2017.42
• Baran, Ilja; Demaine, Erik D .; Pătraşcu, Mihai (2008), „Algorytmy subkwadratowe dla 3SUM” , Algorithmica , 50 (4): 584–596, doi : 10.1007/s00453-007-9036-3 .
• Demaine, Erik D .; Mitchell, Józef SB ; O'Rourke, Joseph (lipiec 2005), „Problem 11: 3SUM Hard Problems” , The Open Problems Project , zarchiwizowane z oryginału w dniu 15.12.2012 , pobrane 02.09.2008 .
• Erickson, Jeff (1999), „Dolne granice problemów liniowej spełnialności” , Chicago Journal of Theoretical Computer Science , MIT Press, 1999 .
• Gajentaan, Anka; Overmars, Mark H. (1995), „O klasie problemów O ( n ² ) w geometrii obliczeniowej”, Geometria obliczeniowa: teoria i zastosowania , 5 (3): 165–185, doi : 10.1016 / 0925-7721 (95 )00022-2 , hdl : 1874/17058 .
• King, James (2004), Badanie trudnych problemów 3SUM (PDF) .