logoalt Hacker News

nightshade1511 • today at 12:18 AM • 1 reply • view on HN

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.


Replies

raegis • today at 2:41 AM

Hey, this is a common error. (2^(n^0.9))^2 is not 2^(n^1.8) but 2^(2 * n^0.9).

➕ show 2 replies