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."

▲

adgjlsfhk1 8 hours ago | parent | next [-]

OTOH, it would be surprising if this sort of technique didn't apply to other NP problems.

▲

jibalt 5 hours ago | parent [-]

It'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.

▲

adgjlsfhk1 4 hours ago | parent [-]

right, 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.

Also 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.

	▲	calf 3 hours ago \| parent [-]
		Yeah that would be interesting, like could there be different NP languages being sub-exponential but for entirely different reasons.

▲

8 hours ago | parent | prev [-]

[deleted]