Hacker News Reader

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

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.

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.

Yeah that would be interesting, like could there be different NP languages being sub-exponential but for entirely different reasons.

Reply on news.ycombinator.com