← Back to context

Comment by kakapo5672

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

20 comments

kakapo5672

Reply
mudita  13 hours 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  13 hours 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  11 hours 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.

      8 replies →

pcstl  13 hours 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  10 hours 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.

IsTom  13 hours 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.