points by Aunche 3 days ago | 0 comments
Suppose 3sat is solved in 2^sqrt(n). That's subexponential. An n^2 reduction from sat to 3sat is polynomial. However, an algorithm using this reduction with the discovered solution, would run in (2^sqrt(n))^2 which is just 2^n.
[–] stbede 3 days ago
[–] raegis 3 days ago
That last statement is not correct. (2^sqrt(n))^2 equals 2^(2 * sqrt(n)). If you just take n=1 in your expression you can see the error, your (2^sqrt(n))^2 yields 4, while 2^n is just 2.
[–] Dylan16807 3 days ago
Yeah but you're fixing the wrong thing. The problem after reduction to 3sat is (2^sqrt(n^2)). The altered n becomes the input to 3sat.
This also means your other comment here is wrong to suggest any error: https://news.ycombinator.com/item?id=50254142
[–] raegis 2 days ago
I was just correcting the statement as written. I see they meant to say something else. You are correct about my other comment--I was in a misdirected, math-correcting rage.
[–] jballanc 3 days ago
...that's...not how exponents work
[–] Dylan16807 3 days ago
The result is right, they wrote the parentheses in the wrong spot, don't be so shocked.
but
2^(sqrt(n)^2) = 2^n