# Why doesn't subset sum solution violate Exponential Time Hypothesis?

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?

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

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.
• @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. – D.W. Jun 23 '16 at 22:03