3SUM问题(或称三数之和问题)是一个计算问题,旨在判断给定的整数或实数集合中是否包含三个互不相同的元素,使其和为零。该问题的一个紧密相关形式涉及三个集合 、 和 ,判断是否存在 、 和 满足 。该问题是计算复杂性研究中的标准基准,在计算几何以及对那些可在多项式时间内求解但被认为需要接近二次时间的问题的研究中尤为重要。
问题表述与基础算法
对于包含 个数的集合,最直接的方法是枚举检验所有三元组,耗时 。一种标准的改进算法是先对这些数进行排序。对于每个元素 ,算法通过两个指针从两端向内移动,在其余已排序的元素中搜索和为 的二元对。在最初的 排序之后,这一步耗时 ,且排序步骤不占主导地位。这一确定性 算法是后续诸多理论研究的基线。
三集合版本可以归约到相同的思路。将 和 中的元素组合,与已排序的 中元素进行匹配,因此运行时间相对于输入规模仍保持二次方。
该问题的变体包括判定版本(是否存在解?)、搜索版本(给出一组解)以及计数版本(统计解的个数)。判定版本研究得最为广泛。对于整数输入,时间复杂度结果取决于计算模型,例如字 RAM(word RAM)、实数 RAM(real RAM)或线性决策树模型。
难度与 3SUM 猜想
1995年,盖扬坦(Gajentaan)和奥弗马斯(Overmars)猜想不存在能在次二次(subquadratic)时间内运行的 3SUM 算法。他们还证明了许多几何问题都可以归约到 3SUM,从而使 3SUM 成为条件性下界的重要来源。若某个问题的次二次算法能导出 3SUM 的次二次算法,则称该问题为 3SUM难(3SUM-hard)。
随后,埃里克森(Erickson)在受限的线性决策树模型下证明了 3SUM 具有 的下界,该模型涵盖了标准的二次算法。不过这一受限结果并未解决允许使用任意操作的通用算法情形。
3SUM 猜想是指 3SUM 无法在强次二次时间内解决的假说,即对于任意固定的 ,不存在 时间的算法。随着时间推移,它与强指数时间假说(SETH)以及全对最短路径(APSP)难度猜想等一同成为细粒度复杂度的核心假说之一。在假定该猜想成立的前提下,许多证明某问题需要二次时间的结果都依赖于 3SUM 难度归约。
次二次算法
该猜想的最初形式已被推翻。2014年,格伦隆德(Grønlund)和佩蒂(Pettie)针对实数 3SUM 给出了一个运行时间为 的确定性算法,以及一个以高概率在 时间内运行的随机化算法。他们还证明了 3SUM 存在使用 4-线性查询、深度为 的决策树。由于这些算法仅节省了对数因子,因而并未带来多项式级别的加速。
在此之前,巴兰(Baran)、德梅因(Demaine)和佩特拉什库(Pătraşcu)在字 RAM 和非认知缓存(cache-oblivious)等多个模型下获得了整数 3SUM 的次二次算法。他们的方法利用哈希技术挖掘了并行性。后续工作进一步改进了这些界限,包括弗罗因德(Freund)以及戈尔德(Gold)和沙里尔(Sharir)的工作,以及陈(Chan)给出的确定性改进,使这些界限更为简洁和紧凑。
鉴于上述结果,该猜想的现代形式限定为不存在强次二次算法,即无法获得多项式因子 级别的加速。这一更强表述的状态目前仍悬而未决,其推论在理论计算机科学界依然被广泛接受。
相关问题
学者们对若干推广和变体展开了深入研究:
- -SUM:寻找和为零的 个数。其复杂度与 3SUM 紧密相关,线性退化性测试等泛化问题也常与之并行分析。
- 卷积 3SUM(Convolution 3SUM):与卷积相关的变体,有时可通过快速傅里叶变换求解,其计算难度与 3SUM 密切相关。
- 带预处理的 3SUM:允许对输入集合的超集进行预处理。陈和莱文斯坦(Lewenstein)证明,经过二次预处理后,可借助加法组合学在真正的次二次时间内解决整数 3SUM 实例。
- 3POL:将求和替换为三变量的常数度多项式。针对 3SUM 的次二次算法推广后同样适用于该问题。相关成果还涵盖了一般位置测试问题(判断平面上 个点中是否有三点共线)。
- 3XOR:将加法替换为按位异或运算,因其与 3SUM 的内在联系而受到关注。
应用与重要意义
3SUM 难度常用于解释计算几何中许多问题所表现出的二次时间屏障,包括若干点线关系和多边形问题。猜想中的计算难度还与图论中的三角形枚举密切相连,该猜想的一个变体为在稀疏图中列出所有三角形提供了下界。动态数据结构和字符串匹配领域的研究也广泛采用了基于 3SUM 的归约。
在实践中,二次算法常用于中等规模的输入;而次二次算法的常数因子较大且对数级节省较小,主要具有理论意义。该问题还推动了随机化算法和并行计算的研究,因为针对整数的最佳次二次成果均利用了并行性和哈希技术。
当前认知局限
对于一般的实数或整数输入,目前尚未发现能在强次二次时间内求解 3SUM 的算法;反之,也未有证明排除此类算法的存在。因此, 上界与猜想的 下界之间的鸿沟仍未填平。依赖于 3SUM 猜想的研究结论均具条件性:它们在猜想为真的前提下成立,若未来出现改善已知界限的新算法,这些结论可能会被削弱甚至推翻。
参考来源
- Deterministic 3SUM-Hardnessarxiv.org
- The monitoring problem for timed automataarxiv.org
- Subquadratic Algorithms for 3SUM Ilya Baran Erik D. Demaine Mihai Pˇatra¸scupeople.csail.mit.edu
- Chapter 16: 3SUM-Hardness: A Method for Obtaining Quadratic Lower Boundscs.umd.edu
- Threesomes, Degenerates, and Love Trianglesarxiv.org
- [1612.02384] Subquadratic Algorithms for Algebraic Generalizations of 3SUMarxiv.org
- Data Structures Meet Cryptography: 3SUM with Preprocessingarxiv.org
- Sumsets, 3SUM, Subset Sum: Now for Real!arxiv.org
- Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy∗†drops.dagstuhl.de
- Improved Subquadratic 3SUMlink.springer.com
- 3SUM, 3XOR, Triangles Zahra Jafargholi∗ Emanuele Viola∗ September 24, 2014ccs.neu.edu