3SUMMA

"3sum" omdirigerar hit. För maltdrycken, se Jämförelse av alkopops § Ölbaserad .

Olöst problem inom datavetenskap :

Finns det en algoritm för att lösa 3SUM-problemet i tid $O(n^{2-\epsilon })$ , för vissa $\epsilon >0$ ?

(fler olösta problem inom datavetenskap)

I beräkningskomplexitetsteorin frågar 3SUM - problemet om en given uppsättning av $n$ reella tal innehåller tre element som summerar till noll. En generaliserad version, k -SUM, ställer samma fråga på k tal. 3SUM kan enkelt lösas i $O(n^{2})$ tid och matchande $\Omega (n^{\lceil k/2 \rceil })$ lägre gränser är kända i vissa specialiserade beräkningsmodeller ( Erickson 1999) .

Det antogs att varje deterministisk algoritm för 3SUM kräver $\Omega (n^{2})$ tid. År 2014 vederlagdes den ursprungliga 3SUM gissningen av Allan Grønlund och Seth Pettie som gav en deterministisk algoritm som löser 3SUM i $O(n) ^{2}/({\log n}/{\log \log n})^{2/3})$ tid. Dessutom visade Grønlund och Pettie att den 4- linjära beslutsträdets komplexitet för 3SUM är $O(n^{3/2}{\sqrt {\log n}})$ . Dessa gränser förbättrades sedan. Den nuvarande mest kända algoritmen för 3SUM körs i $O(n^{2}(\log \log n)^{O (1)}/{\log ^{2}n})$ tid. Kane, Lovett och Moran visade att den 6- linjära beslutsträdets komplexitet för 3SUM är $O(n{\log ^{2}n})$ . Den senare gränsen är snäv (upp till en logaritmisk faktor). Det antas fortfarande att 3SUM är olöslig i $O(n^{2-\Omega (1)})$ förväntad tid.

När elementen är heltal i intervallet $[-N,\dots ,N]$ , kan 3SUM lösas i $O(n +N\log N)$ tid genom att representera ingångsmängden $S$ som en bitvektor , beräkna mängden $S+S$ av alla parvisa summor som en diskret faltning med hjälp av den snabba Fouriertransformen , och slutligen jämföra denna uppsättning med $S$ .

Kvadratisk algoritm

Antag att inmatningsmatrisen är $S[0..n-1]$ . I heltalsmodeller ( $] {\displaystyle S[i] }$ RAM ) kan 3SUM lösas i $O(n^{2})$ tid i genomsnitt genom att infoga varje nummer till en hashtabell och sedan, för varje index $i$ och $j$ , kontrollera om hashtabellen innehåller heltal $- (S[i]+S[j])$ .

Det är också möjligt att lösa problemet samtidigt i en jämförelsebaserad datormodell eller riktig RAM , för vilken hashning inte är tillåten. Algoritmen nedan sorterar först inmatningsmatrisen och testar sedan alla möjliga par i en noggrann ordning som undviker behovet av binär sökning efter paren i den sorterade listan, vilket uppnår värsta fall $O(n^{ 2})$ tid, enligt följande.

             
 sortera(S);  för  i = 0  till  n - 2  gör  a = S[i]; start = i + 1;  slut = n - 1;   medan  (start < slut)  gör  b = S[start] c = S[slut];  om  (a + b + c == 0)  utmata  sedan  a, b, c; // Fortsätt att söka efter alla triplettkombinationer som summeras till noll.  // Vi måste uppdatera både slut och start tillsammans eftersom arrayvärdena är distinkta.  start = start + 1;  slut = slut - 1;   annars  om  (a + b + c > 0)  då  slut = slut - 1;  annars  start = start + 1;  slutändan  _ 

Följande exempel visar denna algoritms exekvering på en liten sorterad array. Aktuella värden för a visas i rött, värden för b och c visas i magenta.

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

Algoritmens riktighet kan ses enligt följande. Anta att vi har en lösning a + b + c = 0. Eftersom pekarna bara rör sig i en riktning kan vi köra algoritmen tills pekaren längst till vänster pekar på a. Kör algoritmen tills någon av de återstående pekarna pekar på b eller c, beroende på vilket som inträffar först. Sedan kommer algoritmen att köras tills den sista pekaren pekar på den återstående termen, vilket ger den jakande lösningen.

Varianter

Icke-noll summa

Istället för att leta efter tal vars summa är 0, är ​​det möjligt att leta efter tal vars summa är vilken konstant C som helst . Det enklaste sättet skulle vara att modifiera den ursprungliga algoritmen för att söka i hashtabellen efter heltal ( $\displaystyle (C-(S[i]+S[j]) )}$ .

En annan metod:

• Subtrahera C /3 från alla element i inmatningsmatrisen.
• I den modifierade arrayen, hitta 3 element vars summa är 0.

Till exempel, om A=[1,2,3,4] och om du blir ombedd att hitta 3SUM för C =4, subtrahera då 4/3 från alla element i A, och lös det på vanligt 3summa sätt, dvs. , $(aC/3)+(bC/3)+(cC/3)=0$ .

Tre olika arrayer

Istället för att söka efter de 3 numren i en enda array kan vi söka efter dem i 3 olika arrayer. Dvs, givet tre arrayer X, Y och Z, hitta tre tal a ∈ X , b ∈ Y , c ∈ Z , så att $a+b+c=0$ . Kalla 1-array-varianten 3SUM×1 och 3-array-varianten 3SUM×3.

Med en lösare för 3SUM×1 kan 3SUM×3-problemet lösas på följande sätt (förutsatt att alla element är heltal):

• För varje element i X , Y och Z , sätt: $X[i]\gets X[i]*10+1$ , $Y[i]\gets Y[i]*10+2$ , $Z[i]\gets Z[ i]*10-3$ .
• Låt S vara en sammanlänkning av arrayerna X , Y och Z .
• Använd oraklet 3SUM×1 för att hitta tre element $'\in S,\ c'\in S}$ att $a'+b'+c'=0$ .
• Returnera $a\gets (a'-1)/10,\ b \gets (b'-2)/10,\ c\gets (c'+3)/10$ .

Genom att vi transformerade arrayerna är det garanterat att a ∈ X , b ∈ Y , c ∈ Z .

Konvolution summa

Istället för att leta efter godtyckliga element i arrayen så att:

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

convolution 3sum -problemet (Conv3SUM) letar efter element på specifika platser:

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

Minskning från Conv3SUM till 3SUM

Med en lösare för 3SUM kan Conv3SUM-problemet lösas på följande sätt.

• Definiera en ny array T , så att för varje index i : $T[i]=2nS[i]+i$ (där n är antalet element i matrisen, och indexen går från 0 till n -1).
• Lös 3SUM på arrayen T .

Korrekthetsbevis:

• Om det i den ursprungliga arrayen finns en trippel med ${\displaystyle S[i+j]=S[i]+S[j]} ,$ då ${ \displaystyle T[i+j]=2nS[i+j]+i+j=(2nS[i]+i)+(2nS[j]+j)=T[i]+T[j]} ,$ så denna lösning kommer att hittas av 3SUM på T .
• Omvänt, om det i den nya arrayen finns en trippel med ${\displaystyle T[k]=T[i]+T[j]} ,$ då $2nS[k]+k=2n(S[i]+S[j])+(i+ j)$ . Eftersom $i+j<2n$ , nödvändigtvis $S[k]=S[i]+S[j]$ och $k=i+j$ , så detta är en giltig lösning för Conv3SUM på S .

Minskning från 3SUM till Conv3SUM

Med en lösare för Conv3SUM kan 3SUM-problemet lösas på följande sätt.

Reduktionen använder en hashfunktion . Som en första approximation, antag att vi har en linjär hashfunktion, dvs en funktion h så att:

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

Antag att alla element är heltal i intervallet: 0... N -1, och att funktionen h mappar varje element till ett element i det mindre intervallet av index: 0... n -1. Skapa en ny array T och skicka varje element av S till dess hashvärde i T , dvs för varje x i S ( ${\displaystyle \forall x\in S} )$ :

$T[h(x)]=x$

Anta först att mappningarna är unika (dvs varje cell i T accepterar endast ett enda element från S ). Lös Conv3SUM på T . Nu:

• Om det finns en lösning för 3SUM: $z=x+y$ , då: ${\ displaystyle T[h(z)]=T[h(x)]+T[h(y)]}$ och $h(z)=h( x)+h(y)$ , så denna lösning kommer att hittas av Conv3SUM-lösaren på T .
• Omvänt, om en Conv3SUM hittas på T , så motsvarar den uppenbarligen en 3SUM-lösning på S eftersom T bara är en permutation av S .

Denna idealiserade lösning fungerar inte, eftersom vilken hashfunktion som helst kan mappa flera distinkta element av S till samma cell i T . Tricket är att skapa en array $T^{*}$ genom att välja ett enda slumpmässigt element från varje cell i T , och köra Conv3SUM på $T^{*}$ . Hittas en lösning så är det en korrekt lösning för 3SUM på S . Om ingen lösning hittas, skapa ett annat slumpmässigt $T^{*}$ och försök igen. Antag att det finns högst R element i varje cell av T . Då är sannolikheten att hitta en lösning (om en lösning finns) sannolikheten att det slumpmässiga urvalet kommer att välja rätt element från varje cell, vilket är ( 1 / $(1/R)^{3}}$ . Genom att köra Conv3SUM $R^{3}$ gånger kommer lösningen att hittas med stor sannolikhet.

Tyvärr har vi ingen linjär perfekt hashing, så vi måste använda en nästan linjär hashfunktion, dvs en funktion h så att:

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

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

Detta kräver att elementen i S dupliceras när de kopieras till T , dvs. sätta varje element $x\in S$ båda i $T[h(x)]$ (som tidigare) och i $T[h(x)]-1$ . Så varje cell kommer att ha 2 R- element, och vi måste köra Conv3SUM $(2R)^{3}$ gånger.

3SUM-hårdhet

Ett problem kallas 3SUM-hårt om att lösa det i subkvadratisk tid innebär en subkvadratisk tidsalgoritm för 3SUM. Begreppet 3SUM-hårdhet introducerades av Gajentaan & Overmars (1995) . De visade att en stor klass av problem inom beräkningsgeometri är 3SUM-hårda, inklusive följande. (Författarna erkänner att många av dessa problem bidrar med andra forskare.)

• Givet en uppsättning linjer i planet, är det tre som möts i en punkt?
• Givet en uppsättning icke-korsande axelparallella linjesegment, finns det en linje som separerar dem i två icke-tomma delmängder?
• Givet en uppsättning oändliga remsor i planet, täcker de helt en given rektangel?
• Med tanke på en uppsättning trianglar i planet, beräkna deras mått.
• Med tanke på en uppsättning trianglar i planet, har deras förening ett hål?
• Ett antal synlighets- och rörelseplaneringsproblem, t.ex.
  • Med tanke på en uppsättning horisontella trianglar i rymden, kan en viss triangel ses från en viss punkt?
  • Givet en uppsättning icke-korsande axel-parallella linjesegmenthinder i planet, kan en given stav flyttas genom translationer och rotationer mellan start- och målpositioner utan att kollidera med hindren?

Vid det här laget finns det en mängd andra problem som faller inom denna kategori. Ett exempel är beslutsversionen av X + Y-sortering : givna uppsättningar av nummer X och Y med n element vardera, finns det n ² distinkta x + y för x ∈ X , y ∈ Y ?

Se även

• Delmängd summa problem

Anteckningar

•   Kane, Daniel M.; Lovett, Shachar; Moran, Shay (2018). "Nästan optimala linjära beslutsträd för k-SUM och relaterade problem". Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC) : 554–563. arXiv : 1705.01720 . doi : 10.1145/3188745.3188770 . ISBN 9781450355599 .
•   Chan, Timothy M. (2018), "Mer logaritmisk-faktorhastigheter för 3SUM, (median, +)-Konvolution och vissa geometriska 3SUM-hårda problem", 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). Trekanter, degenererar och kärlekstrianglar . 2014 IEEE 55:e årliga symposium om grunderna för datavetenskap. sid. 621. arXiv : 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 .
• Guld, Omer; Sharir, Micha (2017), "Förbättrade gränser för 3SUM, k -SUM och linjär degeneration", I Proc. 25:e årliga europeiska symposium om algoritmer (ESA) , LIPIcs, 87 : 42:1–42:13, doi : 10.4230/LIPIcs.ESA.2017.42
• Baran, Ilya; Demaine, Erik D. ; Pătraşcu, Mihai (2008), "Subquadratic algorithms for 3SUM" , Algorithmica , 50 (4): 584–596, doi : 10.1007/s00453-007-9036-3 .
• Demaine, Erik D. ; Mitchell, Joseph SB ; O'Rourke, Joseph (juli 2005), "Problem 11: 3SUM Hard Problems" , The Open Problems Project , arkiverat från originalet 2012-12-15 , hämtat 2008-09-02 .
• Erickson, Jeff (1999), "Lower bounds for linear satisfiability problems" , Chicago Journal of Theoretical Computer Science , MIT Press, 1999 .
• Gajentaan, Anka; Overmars, Mark H. (1995), "On a class of O( n ² ) problems in computational geometry", Computational Geometry: Theory and Applications , 5 (3): 165–185, doi : 10.1016/0925-7721(95) )00022-2 , hdl : 1874/17058 .
• King, James (2004), En undersökning av 3SUM-hårda problem (PDF) .