# Subexponential algorithm for Np-complete problems [duplicate]

https://cstheory.stackexchange.com/a/3627/32204

Could someone explain to me why this reasoning is false. I don't understand it! To me this sounds plausible!

• It's in the answer? – Raphael Feb 24 '15 at 13:54
• Rather, in the last comment of cstheory.stackexchange.com/a/3627/32204. The comment by @RussellImpagliazzo explains why the third bullet of the reasoning in the answer is incorrect. – Wandering Logic Feb 24 '15 at 14:07
• yes i read that comment, but i don't understand the comment. That is the reason i asked the question. – johnZerma Feb 24 '15 at 14:11
• The ETH is that any algorithm for 3SAT must be exponential. If you can reduce 3SAT to NP problem X in polynomial time and space and then solve X, X must be NP complete. But if the size $M$ 3SAT problem is transformed into a size $N=M^2$ X problem, then you could still solve X in time $2^\sqrt{N} = 2^M$ without violating the ETH. Solving a size $M$ 3SAT problem still takes time $2^M$ (exponential), but solving an X problem takes time $2^\sqrt{N}$ (subexponential). – Wandering Logic Feb 24 '15 at 14:15
• Now this makes sense! and what about 3SAT has no pseudo-poly-algorithm but there are NP-complete-problems which have one. Then 3SAT should also have one, since it is reduzible to one.(but it is false) i think there is a different reasoning for this false claim? – johnZerma Feb 24 '15 at 14:24