|
| ▲ | cochne 8 hours ago | parent | next [-] |
| 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] |
|
|
| ▲ | mswphd 7 hours ago | parent | prev | next [-] |
| 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. |
|
| ▲ | jibalt 5 hours ago | parent | prev | next [-] |
| 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. |
|
| ▲ | LPisGood 5 hours ago | parent | prev | next [-] |
| Subexponential(poly(n)) may be exponential in n |
|
| ▲ | dataflow 8 hours ago | parent | prev [-] |
| Did you reduce in the wrong direction or am I misunderstanding what you're trying to say? |
