3SUM problem on integers as hard as on real numbers
3SUM Is Really Hard: A Real-to-Integer Reduction
Data Structures and Algorithms
Summary
The 3SUM problem asks if three numbers in a list add up to zero and is a well-known challenge in computer science. The authors show that if we can solve this problem quickly for whole numbers, then we can also solve it quickly for real numbers. This links two versions of the problem that were thought to be potentially different in difficulty. The proof mixes ideas from optimization and a branch of math called additive combinatorics. This answers an open question about the problem's complexity.
What this means in practice
- •For algorithm designers: Rule out faster algorithms for real-valued 3SUM unless integer 3SUM can also be solved faster.
- •For complexity analysts: Use the reduction to transfer hardness results between real and integer inputs for fine-grained complexity studies.
A theory result. No direct application yet.
Authors
Nick Fischer, Adam Polak, Jonas Schmidt
Abstract
We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued inputs. This answers an open problem posed by Chan, Vassilevska Williams, and Xu [STOC 2022], and constitutes the first such tight real-to-integer self-reduction in fine-grained complexity. Our proof relies on a surprising combination of the Frank--Tardos theorem from optimization with Freiman-type theorems from additive combinatorics.