Help Privacy Policy Disclaimer
  Advanced SearchBrowse





SETH-Based Lower Bounds for Subset Sum and Bicriteria Path


Bringmann,  Karl
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 336KB

Supplementary Material (public)
There is no public supplementary material available

Abboud, A., Bringmann, K., Hermelin, D., & Shabtay, D. (2018). SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. Retrieved from http://arxiv.org/abs/1704.04546.

Cite as: https://hdl.handle.net/21.11116/0000-0002-9E17-3
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
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
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).