Comment

Comment by bluepoint

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.

parent bluepoint 12 days ago

No comments yet

Be the first to share your thoughts.

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton