0
$\begingroup$

Was crawling the internet, and found this in a paper (1)

"[...], a variant of dynamic programming called dynamic dynamic programming has been shown to have a worst-case sub-exponential time complexity of $2^{O(\sqrt x)}$ when the total bit length $x$ of the input set is used as the complexity parameter."

As I understand this claim violates the Exponential Time Hypothesis, and there has been some answers in the forum clearly stating no such sub-exponential algorithm exists, would be interesting to know what the experts in the area think about the proposed algorithm in terms of worst case complexity.

Direct link to the paper (2) explaining the dynamic dynamic approach.

(1) Thomas E. O’Neil -An Empirical Study of Algorithms for the Subset Sum Problem

(2) Thomas E. O’Neil, Scott Kerlin - A Simple $2^{O(\sqrt x)}$ Algorithm for PARTITION and SUBSET SUM

Improve this question
$\endgroup$
4
  • $\begingroup$ Sounds interesting. Can you clarify what your question is? Are you asking for a justification for the running time bound listed? Something else? Not sure what you mean by "the reason". Also, can you edit the question to give a full citation to the paper (title, authors, where published), so that the question still makes sense even if the link stops working, and so that others with a similar question about the paper can find this page by searching on the paper title? Thank you! $\endgroup$
    – D.W. ♦
    Commented Oct 27, 2017 at 4:04
  • $\begingroup$ Let me do the changes $\endgroup$
    – Jesus Salas
    Commented Oct 27, 2017 at 4:08
  • $\begingroup$ If there exists an $o(n^2)$ reduction from SAT to Subset-Sum [and papers are correct], ETH fails. But does such reduction exist? $\endgroup$
    – rus9384
    Commented Oct 27, 2017 at 8:13
  • $\begingroup$ Note: standard reduction from SAT is $\Theta(n^2)$. $\endgroup$
    – rus9384
    Commented Oct 27, 2017 at 8:26

1 Answer 1

Reset to default
1
$\begingroup$

This doesn't violate the exponential time hypothesis. The exponential time hypothesis says that k-SAT takes exponential time, i.e., $\Omega(2^{cn})$ for some constant $c>0$. So if you found a $O(2^{\sqrt{n}})$ time algorithm for k-SAT, that would violate the exponential time hypothesis -- but a a $O(2^{\sqrt{n}})$ time algorithm for subset sum does not violate the hypothesis.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I was thinking this could be the case, thanks for confirming, the sub-exponential worst case question is still there, but this clear out the ETH issue. $\endgroup$
    – Jesus Salas
    Commented Oct 27, 2017 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.