No. NP is always poly time reduceable to 3SAT
replySee 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."
replyOTOH, it would be surprising if this sort of technique didn't apply to other NP problems.
replyIt's not clear what you're trying to say or the relevance. The fact remains that "NP is always poly time reduceable to 3SAT" and "3SAT is sub-exponential" does not imply that NP is sub-exponential.
replyright, but anything linearly reducable to kSAT is trivially sub-exponential, and a discovery like this means that linear reductions are a whole lot more important than they used to be.
replyAlso for NP problems that can't linear reduce to kSAT just having the knowledge that SAT is sub-exponential (and the tools), makes it a lot more likely that we see a whole lot more problems become exponential.
Yeah that would be interesting, like could there be different NP languages being sub-exponential but for entirely different reasons.
replydeleted
replypractically, 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.
replyYour "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.
replyNote https://news.ycombinator.com/item?id=50253213 which explains it better.
Subexponential(poly(n)) may be exponential in n
replyDid you reduce in the wrong direction or am I misunderstanding what you're trying to say?
replydeleted
reply