Hacker News

points by demibabs 3 days ago | 0 comments

No I get that, but I don't get how proving 3SAT can be proved in subexponential time does not imply all NP-complete problems can be as well, since they can all be reduced to 3SAT in polynomial time.

[–] nightshade1511 3 days ago

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.

[–] Aunche 3 days ago

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

(2^sqrt(n))^2 = 2^sqrt(n) * 2^sqrt(n) = 2^(sqrt(n) + sqrt(n)) = 2^(2 sqrt(n))

but

2^(sqrt(n)^2) = 2^n

[–] 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.

[–] caughtinthought 3 days ago

Basically 3SAT algo isn't sub-exponential enough to absorb the arbitrary poly cost for the reduction

So 3SAT+poly reduction ends up being exponential

[–] demibabs 3 days ago

Gotcha, thanks

[–] csheehan10 3 days ago

To achieve this you would need to show that 3SAT is solvable in 2^{n^c} time for every c>0, not just a single c<1.

In this case they have c = 1-0.5(\log \log n)/(\log n) which is approaching 1 for large n.

[–] imadr 3 days ago

Misunderstood your question sorry, I have no idea!