Hacker News
points by bluepoint 1 day ago | 0 comments
I don’t know what you mean by negating the subexponential time. If the reduction is polynomial the time is still dominated by the 3SAT. Btw wikipedia says that the proposed algorithms correspond to 2^(n (log log n)^2/log n) which is subexponential but not in a practical way.

Edit: Ok, I a guess I am wrong if the reduction is n^ log n/(log log n)^2 we are back to exponential.

Aún no hay comentarios.
Hacker News