Hacker News

points by kakapo5672 3 days ago | 0 comments

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 3 days ago

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 3 days ago

I’m not as smart as Scott but for me it’s more like 10% -> 20%. Do we have a prediction market for this?

[–] kibwen 3 days ago

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 3 days ago

Why must prediction markets have a predefined end date?

[–] jibalt 3 days ago

Without it, capital would be trapped indefinitely.

[–] howunfortunate 3 days ago

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

[–] throw-qqqqq 2 days ago

Sure, but in most (all?) financial settings, this would still count as exposure.

It doesn’t matter if I bet $N on something using cash or margin, my exposure is still $N.

Since you can’t have unlimited exposure, this would still lock up capital, until the bet can be resolved.

[–] FeepingCreature 2 days ago

Well, so? Then the prediction market would also price expected resolution time.

[–] Tadpole9181 3 days ago

How would it work otherwise...?

[–] internetter 3 days ago

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

[–] jibalt 3 days ago

It seems highly irrational to bet that your evaluation is more likely than Aaronson's.

[–] lostmsu 2 days ago

Not under the circumstances IMO

[–] pcstl 3 days ago

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 3 days ago

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.

[–] pcstl 2 days ago

Fair, thank you.

[–] IsTom 3 days ago

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 3 days ago

It basically just says that NP is not the same as EXP

[–] jibalt 3 days ago

Note https://news.ycombinator.com/item?id=50253213 which explains it better.