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?

$\endgroup$
  • 2
    $\begingroup$ n goes up by a very big factor when you reduce 3-SAT to subset sum $\endgroup$ – rotia Jun 23 '16 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 Jun 23 '16 at 20:24
  • 2
    $\begingroup$ Isn't it $2^{poly(n)}$, which is exponential? $\endgroup$ – Evil Jun 23 '16 at 20:39
  • $\begingroup$ Exponential - I am sure that this explanation is trustworthy. $\endgroup$ – Evil Jun 23 '16 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 Jun 23 '16 at 22:31
3
$\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.

$\endgroup$
  • $\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 Jun 23 '16 at 21:48
  • $\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. Jun 23 '16 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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