Reducing 3SUM to Convolution-3SUM
Reducing 3SUM to Convolution-3SUM
复制标题
将 3SUM 简化为卷积 3SUM
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Qizheng He
中科院分区：
文献类型：
--
作者：
Timothy M. Chan;Qizheng He
给定 n 个数字的集合 S，3 SUM 问题要求确定是否存在三个元素 a、b、c ∈ S，使得 a + b + c = 0。相关的卷积 -3 SUM 问题要求确定是否存在一对索引 i、j，使得 A [ i ] + A [ j ] = A [ i + j ]，其中 A 是给定的 n 个数字数组。当数字为整数时，Pˇatra¸scu [STOC 2010] 的一篇开创性论文给出了从 3 SUM 到卷积 -3 SUM 的随机减少，后来由 Kopelowitz、Pettie 和 Porat [SODA 2016] 进行了改进，减速因子为 O (log n )。在本文中，我们针对以 U 为界的整数，提出了从 3 SUM 到卷积 -3 SUM 的简单确定性归约。我们还描述了获得进一步改进的减少的其他想法，在随机情况下只有 (log log n ) O (1) 因子减速，在确定性情况下只有 log O (1) U 因子减速。
Given a set S of n numbers, the 3 SUM problem asks to determine whether there exist three elements a, b, c ∈ S such that a + b + c = 0. The related Convolution -3 SUM problem asks to determine whether there exist a pair of indices i, j such that A [ i ] + A [ j ] = A [ i + j ], where A is a given array of n numbers. When the numbers are integers, a randomized reduction from 3 SUM to Convolution -3 SUM was given in a seminal paper by Pˇatra¸scu [STOC 2010], which was later improved by Kopelowitz, Pettie, and Porat [SODA 2016] with an O (log n ) factor slowdown. In this paper, we present a simple deterministic reduction from 3 SUM to Convolution -3 SUM for integers bounded by U . We also describe additional ideas to obtaining further improved reductions, with only a (log log n ) O (1) factor slowdown in the randomized case, and a log O (1) U factor slowdown in the deterministic case.