# Item

ITEM ACTIONSEXPORT

Released

Paper

#### SETH-Based Lower Bounds for Subset Sum and Bicriteria Path

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1704.04546.pdf

(Preprint), 336KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### 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).

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).