Remix.run Logo
▲ kakapo5672 8 hours ago

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.

▲internetter 6 hours ago | parent [-]

Why must prediction markets have a predefined end date?

▲jibalt 5 hours ago | parent | next [-]

Without it, capital would be trapped indefinitely.

▲howunfortunate 4 hours ago | parent [-]

This is not necessarily true, you could have contracts rather than money down

▲jibalt 3 hours ago | parent [-]

[flagged]

▲Tadpole9181 5 hours ago | parent | prev [-]

How would it work otherwise...?

▲internetter 3 hours ago | parent [-]

Anybody can exit their contract by selling their contract to an interested party

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