区間add / 0存在判定 Ω(N^(1.333)) - よすぽの日記 を公開したらhosさんからΩ*(N1.5)の証明が届いたので紹介します。前記事を読んでいることを前提とします。
Conv 3-SUM
3-SUMの wiki の Convolution sumとして紹介されているvariant(の、3array版)を考えます。
- 3つの長さ $N$ の配列 X, Y, Zが与えられる。X[i] + Y[j] = Z[i + j]なる$i, j (0 \le i, j \lt N)$は存在するか？
実はこれと元の3-SUMは、($O(N^{1.999})$ で解けるかという観点で)同じ難易度であることが知られています。
(3-SUM => Conv 3-SUM)の方向の帰着が難しい方向です。
例えば入力がランダムケースならば適当に $\bmod N$ で要素を分類することで帰着できます(関連: https://x.com/jcvbcn/status/1927106217819726132 )。これを発展させ、$N$ に近い $p$ とランダムな基数 $b(0 \le b \lt p)$ を取り、$x$ をグループ $bx \bmod p$ に割り振ることでいい感じに計算量が抑えられるという仕組みのようです。
参考: https://conferences.mpi-inf.mpg.de/adfocs18/karl/3-3SUM.pdf
帰着
サイズ $M = O(N^{3/4})$ のConv 3-SUMが、サイズ $N$ の数列の問題に帰着できることを示せばよいです。
まず、Conv 3-SUMを更に次のvariantへ帰着します(ここの帰着自体は自明ではないが難しくはないです)。
- 3つの(長さ $M^{2/4}$ の配列)の長さ $K = M^{1/4}$ の列 $X = X'_0, X'_1, \cdots, X'_{K-1}, Y, Z$が与えられる。$x + y = z (x \in X_i, y \in Y_j, z \in Z_{i + j})$ なる$i, j, x, y, z$は存在するか？
この問題を数列の問題に帰着します。
数列の初期値として $X'_0$ を $M^{1/3}$ 回連打, $X'_1$ を $M^{1/3}$ 連打, ... としたものを使用します。これの長さは $M^{4/3} = N$です。
各 $Z'_k$ に対する調査が、$O(M)$ クエリで出来ることを示せばよいです。これは以下の手順で可能です。
- 各 $Y'_0, \cdots, Y'_k$ から要素を $M^{1/3}$ ずつ取り出し、これらに対する調査をまとめて行う。これが $O(M^{2/3})$ クエリで出来ることを示せばよい。
- $Y_i$ から取り出した要素を $X_{k - i}$ に加算クエリでマッピングする (計 $O(M^{2/3})$ クエリ)
- $Z_k$ の各要素について、調査クエリを飛ばす (計 $O(M^{2/3})$ クエリ)
- $Y_i$ のマッピングを戻す (計 $O(M^{2/3})$ クエリ)
よって合計 $O(M^{4/3}) = O(N)$ クエリであり、帰着が完了した
