SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
Preprint
Abstract
Subset-Sum and k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. One of the most intriguing open problems in this area is to base the hardness of one of these problems on the other. Our main result is a tight reduction from k-SAT to Subset-Sum on dense instances, proving that Bellman's 1962 pseudo-polynomial $O^{*}(T)$-time algorithm for Subset-Sum on $n$ numbers and target $T$ cannot be improved to time $T^{1-\varepsilon}\cdot 2^{o(n)}$ for any $\varepsilon>0$, unless the Strong Exponential Time Hypothesis (SETH) fails. This is one of the strongest known connections between any two of the core problems of fine-grained complexity. As a corollary, we prove a "Direct-OR" theorem for Subset-Sum under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of $N$ given instances of Subset-Sum is a YES instance requires time $(N T)^{1-o(1)}$. As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria s,t-Path problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset-Sum: On graphs with $m$ edges and edge lengths bounded by $L$, we show that the $O(Lm)$ pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to $\tilde{O}(L+m)$, in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).
Keywords
All Related Versions
This publication has 38 references indexed in Scilit:
- Improved Subquadratic 3SUMAlgorithmica, 2015
- Lower Bounds Based on the Exponential-Time Hypothesis2015
- Hardness of Approximation for Knapsack ProblemsTheory of Computing Systems, 2014
- Subquadratic Algorithms for 3SUMAlgorithmica, 2007
- Dynamic Programming on the Word RAMAlgorithmica, 2003
- Simple analysis of graph tests for linearity and PCPRandom Structures & Algorithms, 2003
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- On a class of O(n2) problems in computational geometryComputational Geometry, 1995
- Reducibility among Combinatorial Problems1972