[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.]
> 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.
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?
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.
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."
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.
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.
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.
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).
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.
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.
Even if all NP problems could be solved in sub-exponential time, it would not imply that NP ≠ EXP. It seems that many people here are confused about what EXP means – it’s the set of all problems that can be solved in at most exponential time, including those in P.
This is not a proof of NP ≠ EXP. NP ≠ EXP would mean that there is a problem that can be solved in exponential time, but not in non-deterministic polynomial time. That’s completely different from what they have shown.
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.
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.
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.
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.
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.
[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.]
> 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.
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?
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.
It doesn't imply NP is sub-exponential, only that 3SAT is. Conversions to other problems can still end up exponential.
[delayed]
No. NP is always poly time reduceable to 3SAT
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."
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.
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.
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.
Subexponential(poly(n)) may be exponential in n
Did you reduce in the wrong direction or am I misunderstanding what you're trying to say?
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).
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.
Not sure about how "natural" Omega(2^(n/sqrt(log(n))) is, but a huge intermediate result would be proving that QP = NP or QP != NP.
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.
Even if all NP problems could be solved in sub-exponential time, it would not imply that NP ≠ EXP. It seems that many people here are confused about what EXP means – it’s the set of all problems that can be solved in at most exponential time, including those in P.
This is not a proof of NP ≠ EXP. NP ≠ EXP would mean that there is a problem that can be solved in exponential time, but not in non-deterministic polynomial time. That’s completely different from what they have shown.
Definitely puts some weight on the P=NP side of the scale!
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.
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)
I’m not as smart as Scott but for me it’s more like 10% -> 20%. Do we have a prediction market for this?
It seems highly irrational to bet that your evaluation is more likely than Aaronson's.
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.
Why must prediction markets have a predefined end date?
Without it, capital would be trapped indefinitely.
Well, so? Then the prediction market would also price expected resolution time.
This is not necessarily true, you could have contracts rather than money down
[flagged]
How would it work otherwise...?
Anybody can exit their contract by selling their contract to an interested party
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.
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.
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.
It basically just says that NP is not the same as EXP
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.
Subexponential time still can mean much larger than polynomial time. There's a huge space between the two.
It’s not that it isn’t quite p=np; it actually isn’t p=np.
Still, an impressive accomplishment.
no. It's huge.