0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ It's in the answer? $\endgroup$ – Raphael Feb 24 '15 at 13:54
  • $\begingroup$ 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. $\endgroup$ – Wandering Logic Feb 24 '15 at 14:07
  • $\begingroup$ yes i read that comment, but i don't understand the comment. That is the reason i asked the question. $\endgroup$ – johnZerma Feb 24 '15 at 14:11
  • $\begingroup$ 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). $\endgroup$ – Wandering Logic Feb 24 '15 at 14:15
  • $\begingroup$ 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? $\endgroup$ – johnZerma Feb 24 '15 at 14:24