论文标题
3LDT和CORV3LDT的非平凡变体之间的等价
Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
论文作者
论文摘要
流行的3sum猜想指出，没有强大的子限定时间算法来检查给定的整数是否包含三个不同的元素$ x_1，x_2，x_3 $，因此$ x_1+x_1+x_2 = x_3 $。一个密切相关的问题是检查给定的整数集是否包含满足$ x_1+x_2 = 2x_3 $的不同元素。这可以在几乎线性的时间内将其简化为3sum，但是令人惊讶的是，尚不清楚建立3sum硬度的反向减少。 我们提供了这样的减少，从而解决了埃里克森的公开问题。实际上，我们考虑了一个更通用的问题，称为3LDT参数为整数参数$α_1，α_2，α_3$和$ t $。在此问题中，我们需要检查给定的整数是否包含不同的元素$ x_1，x_2，x_3 $，以便$α_1x_1 x_1 +α_2x_2 x_2 +α_3x_3 = t $。我们证明，对于某些$ c \ geq2 $，在同一宇宙$ [-n^c，n^c] $上的所有非平凡变体在下降低下都是等效的。我们证明中使用的主要技术工具是著名的Behrend构造的应用，该构造将给定的整数划分为几个避免选择线性方程的子集。 我们将结果扩展到conv3ldt并表明，对于所有$ c \ geq2 $，在宇宙上所有3 dldt的非平凡变体$ [ - n^c，n^c] $和conv3ldt在宇宙上$ [ - n^{c-1}，n^{c-1}，n^{c-1}]，n^{c-1}] $ subsepations subsepations suberections subertions suefive ye Equivive ye sore corevival soovival soovival yes usemecivivival yes usemecival ye sore con。 最后，我们展示了如何应用Fischer等人的方法。为了表明我们可以将3LDT（CORV3LDT）的非平凡变体降低到任意宇宙中的同一（二次）宇宙的相同变体。
The popular 3SUM conjecture states that there is no strongly subquadratic time algorithm for checking if a given set of integers contains three distinct elements $x_1, x_2, x_3$ such that $x_1+x_2=x_3$. A closely related problem is to check if a given set of integers contains distinct elements satisfying $x_1+x_2=2x_3$. This can be reduced to 3SUM in almost-linear time, but surprisingly a reverse reduction establishing 3SUM hardness was not known. We provide such a reduction, thus resolving an open question of Erickson. In fact, we consider a more general problem called 3LDT parameterized by integer parameters $α_1, α_2, α_3$ and $t$. In this problem, we need to check if a given set of integers contains distinct elements $x_1, x_2, x_3$ such that $α_1 x_1+α_2 x_2 +α_3 x_3 = t$. We prove that all non-trivial variants of 3LDT over the same universe $[-n^c,n^c]$ for some $c\geq2$ are equivalent under subquadratic reductions. The main technical tool used in our proof is an application of the famous Behrend's construction that partitions a given set of integers into few subsets that avoid a chosen linear equation. We extend our results to Conv3LDT and show that for all $c\geq2$, all non-trivial variants of 3LDT over the universe $[-n^c,n^c]$ and of Conv3LDT over the universe $[-n^{c-1},n^{c-1}]$ are subquadratic-equivalent, so in particular they are all equivalent to 3SUM under subquadratic reductions. Finally, we show how to apply the methods of Fischer et al. to show that we can reduce non-trivial variant of 3LDT (Conv3LDT) over an arbitrary universe to the same variant over cubic (quadratic) universe.
