3SUM

コンピュータサイエンスにおける未解決問題

3SUM問題を時間内に解くアルゴリズムはありますか？ ${\displaystyle O(n^{2-\epsilon })}$一部の人にとって${\displaystyle \epsilon >0}$？

コンピュータサイエンスにおける未解決問題

計算複雑性理論では、3SUM問題は、与えられた集合が${\displaystyle n}$実数には合計がゼロになる3つの要素が含まれています。一般化されたバージョンでは、${\displaystyle k}$-SUM は、同じ質問をします${\displaystyle k}$要素は単に3ではなく、3SUMは簡単に解くことができます。${\displaystyle O(n^{2})}$時間、そしてマッチング${\displaystyle \Omega (n^{\lceil k/2\rceil })}$計算の 特殊なモデルでは下限が知られています（Erickson 1999 ）。

3SUMの決定論的アルゴリズムには、${\displaystyle \オメガ (n^{2})}$時間。2014年、アラン・グロンルンドとセス・ペティは、3SUMを解く決定論的アルゴリズムを提示し、元の3SUM予想を反駁した。${\displaystyle O(n^{2}/({\log n}/{\log \log n})^{2/3})}$時間。^{[ 1 ]}さらに、GrønlundとPettieは、 3SUMの 4線形決定木の複雑さが${\displaystyle O(n^{3/2}{\sqrt {\log n}})}$これらの境界はその後改善された。^{[ 2 ] [ 3 ] [ 4 ]} 3SUMの現在最もよく知られているアルゴリズムは、${\displaystyle O(n^{2}(\log \log n)^{O(1)}/{\log ^{2}n})}$時間。^{[ 4 ]} ケイン、ロベット、モランは、3SUM の 6 線形決定木の複雑さが${\displaystyle O(n{\log ^{2}n})}$[ ^{5 ]}後者の境界は（対数因子を除いて）タイトである。3SUMは解けないと依然として推測されている^。${\displaystyle O(n^{2-\オメガ (1)})}$予想時間。^{[ 6 ]}

要素が範囲内の整数である場合${\displaystyle [-N,\dots ,N]}$3SUMは、${\displaystyle O(n+N\log N)}$入力セットを表現することで時間${\displaystyle S}$ビットベクトルとして、セットを計算する${\displaystyle S+S}$すべてのペアワイズ和を高速フーリエ変換を用いた離散畳み込みとして表し、最後にこのセットを${\displaystyle S}$[ ^{7 ]​}

入力配列が${\displaystyle S[0..n-1]}$整数（ワード RAM）モデルの計算では、3SUM は次のように解くことができます。${\displaystyle O(n^{2})}$各数値を挿入して平均時間を計算する${\displaystyle S[i]}$ハッシュテーブルに変換し、次に各インデックスに対して${\displaystyle i}$そして${\displaystyle j}$ハッシュテーブルに整数が含まれているかどうかを確認します${\displaystyle -(S[i]+S[j])}$。

ハッシュ化が許可されていない比較ベースの計算モデルまたは実際の RAMでも、同じ時間で問題を解決できます。以下のアルゴリズムは、まず入力配列をソートし、次にすべての可能なペアをペアごとのバイナリサーチの速度低下を回避する慎重な順序でテストし、最悪の場合で を達成します。${\displaystyle O(n^{2})}$時間は以下のとおりです。^{[ 8 ]}

sort(S); for i = 0 to n - 2 do a = S[i]; 開始 = i + 1; end = n - 1; while (start < end) do b = S[開始] c = S[end]; (a + b + c == 0)の場合、a、b、cを出力する。 // 合計がゼロになるすべての3つ組の組み合わせを引き続き検索します。 // 配列の値は異なるため、開始と終了の両方を同時に更新する必要があります。 開始 = 開始 + 1; end = end - 1; そうでなければ、 (a + b + c > 0)ならば end = end - 1; それ以外 開始 = 開始 + 1; 終わり終わり

以下の例は、このアルゴリズムを小さなソート済み配列に対して実行した結果を示しています。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 を指すまでアルゴリズムを実行します（どちらか早い方）。その後、最後のポインタが残りの項を指すまでアルゴリズムが実行され、肯定的な解が得られます。

問題を3SUM困難と呼ぶのは、その問題を2次時間未満で解くことが、 3SUMに対する2次時間未満アルゴリズムの存在を意味する場合である。3SUM困難性の概念は、GajentaanとOvermars（1995）によって導入された。彼らは、計算幾何学における多くの問題が3SUM困難であることを証明しており、その中には以下の問題が含まれる。（著者らは、これらの問題の多くは他の研究者によって貢献されたものであることを認めている。）

• 平面上の直線群が与えられたとき、一点で交わる直線は3本存在するか？
• 互いに交わらない軸平行な線分の集合が与えられたとき、それらを2つの空でない部分集合に分割する線分は存在するか？
• 平面上に無限に広がる帯状の領域が与えられたとき、それらは与えられた長方形を完全に覆うことができるか？
• 平面上の三角形の集合が与えられたとき、それらの三角形の大きさを計算しなさい。
• 平面上の三角形の集合が与えられたとき、それらの和集合には穴が存在するか？
• 視界や動作計画に関する多くの問題、例えば、
  • 空間内に水平に配置された複数の三角形が与えられたとき、特定の点から特定の三角形を見ることができるか？
  • 平面上に、互いに交差しない軸平行線状の障害物が複数存在する場合、与えられた棒を、それらの障害物と衝突することなく、開始位置と終了位置の間で並進運動と回転運動によって移動させることは可能か？

現在では、このカテゴリーに分類される他の問題が多数存在します。例としては、X + Y ソートの決定版があります。n個の要素を持つ数値の集合XとYが与えられたとき、 x ∈ X、y ∈ Yに対してn ² 個の異なるx + yが存在するか？^{[ 11 ]}

• 部分和問題

• Kane, Daniel M.; Lovett, Shachar; Moran, Shay (2018)、「k-SUM および関連問題に対するほぼ最適な線形決定木」、第 50 回 ACM SIGACT 理論計算機科学シンポジウム議事録、pp. 554–563、arXiv : 1705.01720、doi : 10.1145/3188745.3188770、ISBN  9781450355599S2CID 30368541​ 
• Chan, Timothy M. (2020)、「3SUM、(median,+)-畳み込み、およびいくつかの幾何学的3SUM困難問題に対するさらなる対数係数の高速化」、ACM Transactions on Algorithms、16 (1) 7: 1–23、doi : 10.1145/3363541、MR 4060405 
• Grønlund, Allan; Pettie, Seth (2018)、「スリーサム、退廃的、そして三角関係」、Journal of the ACM、65 (4) 22: 1–25、arXiv : 1404.0799、doi : 10.1145/3185378、MR 3795516 
• Freund, Ari (2017)、「改良された準二次3SUM」、Algorithmica、44 (2): 440–458、doi : 10.1007/s00453-015-0079-6、S2CID 253979651 。
• ゴールド、オメル; Sharir、Micha (2017)、「3SUM、 k -SUM、および線形縮退の境界の改善」、Pruhs、Kirk。 Sohler、Christian (編)、第 25 回アルゴリズムに関する欧州年次シンポジウム、ESA 2017、2017 年 9 月 4 ～ 6 日、オーストリア、ウィーン、LIPIcs、vol.  87、Schloss Dagstuhl – Leibniz-Zentrum für Informatik、pp.  42:1–42:13、doi : 10.4230/LIPICS.ESA.2017.42、ISBN 978-3-95977-049-1S2CID 691387​ 
• バラン、イリヤ。エリック・D・ディメイン; Pătraşcu、Mihai (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年7月)、「問題11：3SUM難問」、The Open Problems Project 、 2008年9月2日取得{{citation}}: CS1 maint: 非推奨のアーカイブサービス (リンク)。
• エリクソン、ジェフ（1999）「線形充足可能性問題の下限」、シカゴ理論計算機科学ジャーナル、1999年、MIT Press。
• Gajentaan, Anka; Overmars, Mark H. (1995), "計算幾何学におけるO( n ^{2 )問題の一種について",} Computational Geometry: Theory and Applications , 5 (3): 165–185 , doi : 10.1016/0925-7721(95)00022-2 , hdl : 1874/17058。
• King, James (2004), 3SUM困難問題に関する調査(PDF)。