2026-07-20T09:01:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22683 2026-04-17T05:32:16Z ddc:004 open_access

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Linear Integer Arithmetic Gokaj, Geri Künnemann, Marvin fine-grained complexity theory descriptive complexity presburger arithmetic completeness results k-SUM In the last three decades, the k-SUM hypothesis has emerged as a satisfying explanation of long-standing time barriers for a variety of algorithmic problems. Yet to this day, the literature knows of only few proven consequences of a refutation of this hypothesis. Taking a descriptive complexity viewpoint, we ask: What is the largest logically defined class of problems captured by the k-SUM problem? To this end, we introduce a class FOP_ℤ of problems corresponding to deciding sentences in Presburger arithmetic/linear integer arithmetic over finite subsets of integers. We establish two large fragments for which the k-SUM problem is complete under fine-grained reductions: 1) The k-SUM problem is complete for deciding the sentences with k existential quantifiers. 2) The 3-SUM problem is complete for all 3-quantifier sentences of FOP_ℤ expressible using at most 3 linear inequalities. Specifically, a faster-than-n^{⌈k/2⌉ ± o(1)} algorithm for k-SUM (or faster-than-n^{2 ± o(1)} algorithm for 3-SUM, respectively) directly translate to polynomial speedups of a general algorithm for all sentences in the respective fragment. Observing a barrier for proving completeness of 3-SUM for the entire class FOP_ℤ, we turn to the question which other - seemingly more general - problems are complete for FOP_ℤ. In this direction, we establish FOP_ℤ-completeness of the problem pair of Pareto Sum Verification and Hausdorff Distance under n Translations under the L_∞/L₁ norm in ℤ^d. In particular, our results invite to investigate Pareto Sum Verification as a high-dimensional generalization of 3-SUM. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Geri Gokaj and Marvin Künnemann 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.55 urn:nbn:de:0030-drops-226835 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.55 eng https://creativecommons.org/licenses/by/4.0/legalcode