Comment by cochne
13 hours ago
It doesn't imply NP is sub-exponential, only that 3SAT is. Conversions to other problems can still end up exponential.
13 hours ago
It doesn't imply NP is sub-exponential, only that 3SAT is. Conversions to other problems can still end up exponential.
Yeah, I was wrong. Page two too, I commented too soon.
NP is not yet proven to be subexponential but still, ETH disproven is huge
No. NP is always poly time reduceable to 3SAT
See this from the paper: "Note that runtime bounds of the form 2^o(n) do not transfer under general polynomial-time reductions (2^n^o(1) would be needed for this), so our result does not imply that general NP problems admit subexponential time algorithms."
OTOH, it would be surprising if this sort of technique didn't apply to other NP problems.
3 replies →
practically, a poly-time reduction can increase teh size of hte problem instance. So maybe you transform a 3-color instance (graph on n vertices) into a n^2 sized SAT instance. You can then solve this in time 2^{n^2 / sqrt{log{n^2}}}, but this is not sub-exponential.
Your "No" is wrong. As he said, "Conversions to other problems can still end up exponential", so (NP is poly time reduceable to 3SAT + 3SAT is sub-exponential) does not imply that NP is sub-exponential -- the cost of the reduction may be enough to push the conjunction from sub-exponential to exponential.
Note https://news.ycombinator.com/item?id=50253213 which explains it better.
Subexponential(poly(n)) may be exponential in n
Did you reduce in the wrong direction or am I misunderstanding what you're trying to say?