Reduction from k-SAT to Subset Sum: Revision history

Jump to navigation Jump to search

Diff selection: Mark the radio buttons of the revisions to compare and hit enter or the button at the bottom.
Legend: (cur) = difference with latest revision, (prev) = difference with preceding revision, m = minor edit.

    15 February 2023

    • curprev 11:1911:19, 15 February 2023‎ Admin talk contribs‎ 544 bytes +544‎ Created page with "FROM: k-SAT TO: Subset Sum == Description == == Implications == assume: SETH<br/>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 Algorit..."
Retrieved from "https://algorithm-wiki.csail.mit.edu/wiki/Reduction_from_k-SAT_to_Subset_Sum"