Hacker News
points by nightshade1511 3 days ago | 0 comments
Suppose 3SAT can be solved in 2^(n^0.9) time (this is not the actual bound in paper). And another NP problem can be reduced to 3SAT in polynomial time, but the reduction increases the problem size from n to n^2. Then after the reduction the other NP problem can solved in 2^(n^1.8) time, so it does not mean all np problems are sub exponential.
[–] raegis 3 days ago
Hey, this is a common error. (2^(n^0.9))^2 is not 2^(n^1.8) but 2^(2 * n^0.9).
[–] raegis 2 days ago
Apologies, I'm incorrect. I misread your math.