logoalt Hacker News

demibabs • today at 12:01 AM • 5 replies • view on HN

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.


Replies

nightshade1511 • today at 12:18 AM

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.

➕ show 1 reply
Aunche • today at 12:21 AM

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.

➕ show 3 replies
caughtinthought • today at 12:08 AM

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

➕ show 1 reply
csheehan10 • today at 3:38 AM

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 • today at 12:07 AM

Misunderstood your question sorry, I have no idea!