1セットが[n ^ 1.99]にあるときの準二次3SUM

Chan
and Lewenstein (STOC 2015)
said:

3つの整数セットの3SUMは、1セットだけが$ [n ^ {2- delta}] $にあると見なされる場合でも解決できます
  準二次的な時間で(いくつかのFFTを実行することによって、相加的な組み合わせを必要とせずに
  読者に)

他の2つのセットは$ [n ^ {3 + o(1)}] $であることに注意してください。

それにもかかわらず、私はこの運動をどのように解決するのか分かりません。何かヒントはありますか?
(たぶんあなたは彼らの論文を使うことができますが、それは過剰なもののようです)

ベストアンサー

私はこの問題を次のように解決できると思います。 3つの集合$ A、B、C $の整数、$ | A | = | B | = | C
| = n $、$ C subseteq [n ^ {2- delta}] $があるとします。我々は、$ a + b + c
= 0 $となるように、C $のA、b 、B、c に$ a が存在するかどうかを確認したい。

まず、集合$ A $を$ k leq n $個の集合$ A_1、 ldots A_k $に分割する。各$ A_i
$は長さ$ n ^ {2- delta} $の区間を含む。今度は集合$ B $から集合$ B_1、 ldots、B_k
$を以下のように構築する。 $ B_i $には、$ [ – n ^ {2- delta} – max_ {a in
A_i} {a}、 – min_ {a in A_i} a] $の$ B $からの数字が入ります。このようにして、$ B
$の各数値は多くても2セット$ B_i $に現れます。そして今、我々は、ある$ i $が$ A_i + B_i + C
$の解が存在するかどうかを調べるだけでよい。

$ a_i = | A_i | $、$ b_i = | B_i | $とする。 $ a_i geq n ^ {1-
delta/2} $または$ b_i geq n ^ {1- delta/2} $ならば、時間$ Oでn個のA_i + B_i
+ C $をFFTで解く^ {2- デルタ} log {n})$です。 (3つすべての集合の数は長さ$ O(n ^ {2-
delta})$の間隔にあるので、$ sum_i a_i = n $と$ sum_i b_i leq 2n $となるので、
$ a_i $と$ b_i $は最大$ 3n ^ { delta/2} $です。つまり、このステップの実行時間は$ O(n ^
{2- delta/2} log {n})です。 $。

$ i $の残りの値については、A_i $と$ b のすべての$ a をB_i $で試し、$ C
$の対数を対数時間で調べることで問題を解決します。このステップでは、$ sum a_i b_i log {n} leq
O(n ^ {2- delta/2} log {n})$という時間がかかります。 (標準的な3-SUMトリックを使って、$
log {n} $をここから削ることができます)

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です