| ▲ | lisper 8 hours ago |
| This seems huge, like not quite p=np but in the same league. Am I missing something ? |
|
| ▲ | krackers 8 hours ago | parent | next [-] |
| [deleted, originally wrote the hypothesis being true would imply NP=EXPTIME which is wrong, since there can be problems in EXPTIME which aren't in NP. And the result that it's now false apparently doesn't imply NP!=EXPTIME either since it seems not strongly subexponential enough to offset the expansion in variables from reductions. See the other comments for a much better explanation.] |
| |
| ▲ | eru 8 hours ago | parent | next [-] | | > Instead we now know that NP is a strict subset of EXP (there are problems in NP that can be solved in subexponential time). It's a bit more complicated than that, if you want to be careful. Sorting is in both NP and EXP and can be solved in subexponential time. I think what they proved is that no problem in NP takes exponential time to solve. (Because you can always reduce them to SAT in polynomial time, and then solve SAT in subexponential time.) EDIT: apparently the runtime bounds they gave here don't survive the usual polynomial reductions, thus they haven't proven that NP != EXP, it seems. | | | |
| ▲ | luc4 8 hours ago | parent | prev [-] | | I mean the result that k-SAT cannot be solved in 2^{o(n)} clearly would imply P!=NP, but how does ETH imply NP = EXP? And how does \neg ETH imply NP != EXP? | | |
|
|
| ▲ | lynndotpy 8 hours ago | parent | prev | next [-] |
| If I am understanding this correctly (and I am still reading this!) and if this is true, this means NP is sub-exponential. Sub-exponential does not mean P=NP. But yes, this is huge if true. This means hard problems aren't as hard as we thought, and it's still possible P=NP. If it turns out to be true P=NP, we're a little closer to that. (I hope P!=NP!) Every paper which assumes ETH is true might now have their conclusions be disproven. |
| |
| ▲ | cochne 8 hours ago | parent [-] | | It doesn't imply NP is sub-exponential, only that 3SAT is. Conversions to other problems can still end up exponential. | | |
| ▲ | wbl 8 hours ago | parent | next [-] | | No. NP is always poly time reduceable to 3SAT | | |
| ▲ | 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? |
| |
| ▲ | 8 hours ago | parent | prev [-] | | [deleted] |
|
|
|
| ▲ | jaggederest 8 hours ago | parent | prev | next [-] |
| This defeats a few hypotheses that were widely relied on. strong exponential time hypothesis, and the titular exponential time hypothesis It's not saying that these problems are easy, but it does demonstrate that they are much easier than previously believed. A decade ago if a human had published this kind of thing, and importantly if it held up, they would be almost certainly a strong candidate for some sort of award(s). |
| |
| ▲ | thatoneengineer 8 hours ago | parent [-] | | Assuming P != NP (and that this NP != EXP proof holds up), what's the next most "natural" candidate for how fast NP must grow? This paper appears to show Omega(2^(n/sqrt(log(n))) with a couple additional fudge factors which would be a very disappointing answer. | | |
| ▲ | jibalt 5 hours ago | parent | next [-] | | This is not a proof that NP != EXP. 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. | |
| ▲ | zeroonetwothree 8 hours ago | parent | prev [-] | | Definitely puts some weight on the P=NP side of the scale! |
|
|
|
| ▲ | kakapo5672 8 hours ago | parent | prev | next [-] |
| My (very amateur) interpretation is that this weakens confidence in P!=NP. Would like to hear from some experts in this area, if this is so or not. |
| |
| ▲ | mudita 8 hours ago | parent | next [-] | | Scott Aaronson comments on his blog "Given this news, I’ll up my personal probability of P=NP from 3% to 5%." (https://scottaaronson.blog/?p=10239#comment-2042428) | | |
| ▲ | zeroonetwothree 8 hours ago | parent [-] | | I’m not as smart as Scott but for me it’s more like 10% -> 20%. Do we have a prediction market for this? | | |
| ▲ | jibalt 5 hours ago | parent | next [-] | | It seems highly irrational to bet that your evaluation is more likely than Aaronson's. | |
| ▲ | kibwen 6 hours ago | parent | prev | next [-] | | Predictions markets are terrible mechanisms for this, because they require imposing an arbitrary time limit at which point the prediction will pay out. IOW, even if you religiously believed P=NP, but you think it would take at least two years to prove it, you would vote against the prediction if the deadline were one year. | | | |
| ▲ | 7 hours ago | parent | prev [-] | | [deleted] |
|
| |
| ▲ | pcstl 8 hours ago | parent | prev | next [-] | | This proves that EXP != NP, which was a stronger claim than P != NP. In a way it shows that NP is perhaps less distant from P than imagined. Whether it can be _reduced_ to P in some gigabrain way, or whether that can be shown to be impossible remains to be seen. It is definitely progress towards an answer to P ?= NP. | | |
| ▲ | jibalt 5 hours ago | parent | next [-] | | This is not a proof that NP != EXP. 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. | |
| ▲ | 8 hours ago | parent | prev [-] | | [deleted] |
| |
| ▲ | IsTom 8 hours ago | parent | prev | next [-] | | There's a chain of classes P, NP(aka Sigma_1), Sigma_2, .., Sigma_n, ... PSPACE, EXPTIME. What we know for sure is that P < EXPTIME, others are unknown (well, maybe this paper adds something to this, time will tell). It's conceivable that each of them is smaller than the next, but also that e.g. P < NP = all the sigmas < PSPACE < EXPTIME or many other possibilities. I think the general consensus is that it's more likely that there are more inequalities than not, but the fact is that we can't even show that P is less than PSPACE so far, which would be extraordinarily surprising if it were true. | |
| ▲ | caughtinthought 8 hours ago | parent | prev [-] | | It basically just says that NP is not the same as EXP | | |
| ▲ | jibalt 5 hours ago | parent [-] | | This is not a proof that NP != EXP. 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. |
|
|
|
| ▲ | amelius 8 hours ago | parent | prev | next [-] |
| Subexponential time still can mean much larger than polynomial time. There's a huge space between the two. |
|
| ▲ | odyssey7 8 hours ago | parent | prev | next [-] |
| It’s not that it isn’t quite p=np; it actually isn’t p=np. Still, an impressive accomplishment. |
|
| ▲ | adgjlsfhk1 8 hours ago | parent | prev [-] |
| no. It's huge. |
