2
$\begingroup$

The quickest algorithm for solving subset sum currently is $2^{n/2}$ (via Wiki). Why doesn't this violate the Exponential Time Hypothesis which states that “there is no family of algorithms that can solve 3-SAT in $2^{o(n)}$ time.”

Couldn't a 3-SAT problem be translated to a subset sum problem in polynomial time and then solved in $2^{n/2}$ time. What am I missing here?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ n goes up by a very big factor when you reduce 3-SAT to subset sum $\endgroup$
    – rotia
    Commented Jun 23, 2016 at 20:15
  • $\begingroup$ Well it also says that any related NP-complete problem (i.e. subset sum) cannot be solved in subexponential time. Isn't 2^(n/2) subexponential? $\endgroup$
    – C Shreve
    Commented Jun 23, 2016 at 20:24
  • 2
    $\begingroup$ Isn't it $2^{poly(n)}$, which is exponential? $\endgroup$
    – Evil
    Commented Jun 23, 2016 at 20:39
  • $\begingroup$ Exponential - I am sure that this explanation is trustworthy. $\endgroup$
    – Evil
    Commented Jun 23, 2016 at 21:07
  • $\begingroup$ n/2 is not o (n). It is O (n). Little-o versus Big-O. $2^{n/2}$ is not subexponential. It is larger than $1.4^n$. $\endgroup$
    – gnasher729
    Commented Jun 23, 2016 at 22:31

1 Answer 1

Reset to default
4
$\begingroup$

Given a 3SAT problem of size $n$, you can convert that to a subset sum problem of size $n^2$ (roughly). Now you can apply the algorithm for subset sum to solve the subset sum in time $2^{n^2/2}$ (roughly). Remember, the running time depends on the size (length) of the input, and here the size of the input will be $n^2$, yielding the $2^{n^2/2}$ figure.

That will give you an algorithm for solving a 3SAT problem of size $n$ in $2^{n^2/2}$ time (roughly). But that's much worse than the naive algorithm, which takes $2^n$ time: $2^n$ is much smaller than $2^{n^2/2}$. So this reduction does not contradict the exponential time hypothesis: it doesn't give you a way to solve 3SAT faster than $2^n$ time.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Ok. I buy that - transformation from 3SAT to SUBSET SUM yields n^2 and the result would be 2^(n^2/2). But the Exponential Time Hypothesis also says that any NP-complete problem cannot be solved in subexponential time. I guess 2^N/2 is not considered subexponential? $\endgroup$
    – C Shreve
    Commented Jun 23, 2016 at 21:48
  • 2
    $\begingroup$ @CShreve, the ETH doesn't say that. Read it again. $2^{n/2}$ time is not subexponential. ETH talks about SAT, not all NP-complete problems, and it talks about $2^{o(n)}$, and $n/2$ is not $o(n)$. See en.wikipedia.org/wiki/Exponential_time_hypothesis, cs.stackexchange.com/q/9813/755. Please don't use the comments to ask follow-up questions or for extended discussion. $\endgroup$
    – D.W. ♦
    Commented Jun 23, 2016 at 22:03
  • $\begingroup$ @D.W. So is there a $poly(2^{\sqrt n})$ time algorithm for subset sum? It wont violate ETH right? $\endgroup$
    – VS.
    Commented Feb 6, 2020 at 16:34

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.