Reduction from k-SAT to Subset Sum

FROM: k-SAT TO: Subset Sum

Implications

assume: SETH
then: for any $\epsilon > {0}$ there exists a $\delta > {0}$ such that Subset Sum is not in time $O(T^{1-\epsilon}{2}^{\delta n})$, and $k$-Sum is not in time $O(T^{1-\epsilon}n^{\delta k})$

Year

2022

Reference

Abboud, A., Bringmann, K., Hermelin, D., & Shabtay, D. (2022). SETH-based lower bounds for subset sum and bicriteria path. ACM Transactions on Algorithms (TALG), 18(1), 1-22.

https://dl.acm.org/doi/full/10.1145/3450524