Does P = NP?
Does P = NP?
➕
Plus
104
Ṁ16k
3000
9%
chance
This market will resolve once a widely-accepted proof exists that P does or does not equal NP. https://en.wikipedia.org/wiki/P_versus_NP_problem
Get
Ṁ1,000
and
S3.00


Sort by:
1y

"In this paper, by constructing extremely hard examples of CSP (with large domains) and SAT (with long clauses), we prove that such examples cannot be solved without exhaustive search, which is stronger than P ̸= NP."
[2302.09512] SAT Requires Exhaustive Search (arxiv.org)

Is it valid? I'm not qualified.

predictedNO 1y

almost definitely not

predictedNO 1y
1y

Can't wait till someone buys 10000M worth of YES and everyone starts guessing if they have insider knowledge.

1y

This market has a different concensus then these 2 https://manifold.markets/LarsDoucet/p-np https://manifold.markets/LarsDoucet/p-np-537cbc88aa90. They predict an 11% - 2 % ratio on P=NP ending up true. Does anyone know how to do market abtirage?

predictedNO 1y

@fejfo There's not enough mana in these markets to really be worth it, but I just fixed it for you. :)

1y

This market is highly unlikely to resolve in the next 10 years and thus is likely not worth betting on for most people.

predictedNO 1y

@AdriaGarrigaAlonso you get your mana back with loans so its fine. all markets that take longer than a month or two to resolve are the same expensiveness; though I suppose you could argue that other long-term markets than this one are better investments. Which is fair, though I think 5% is probably a little high here.

predictedNO 1y

@AdriaGarrigaAlonso There's always an effect, but:

2y

Well, we have to remember that by the Halting problem, there exist a class of problems that are completely undecidable by the language in which they are expressed. So either we will prove it (true or false) by incorporating some new axiom or we will discover the proof from the current axioms. Given the complexity surrounding this proof, I think a better wager would be something like will we find a proof in the next ten years.

predictedNO 2y

@GanymedeAI Meh. That gets too intertwined with predictions on the speed of technological progress. I care about what the answer truly is, not when it's found.

(Lars has some markets on whether a proof is found in the next 5 years.)

predictedNO 2y

@IsaacKing

Sounds reasonable

Will check that out 🙂

predictedNO 2y

Related:

2y
If humanity survives the next 100 years, I would be quite surprised if we did not get a proof within that time.
given that chances that it will resolve correctly are minimal (P!=NP but I am not expecting proof in my lifetime), and payout is much higher for YES in other words, this is a poor match for prediction markets
2y
I mean, P does not equal NP. It won’t get proven anytime soon, but it’s still worth betting my entire loan.
2y
I have a proof, but it does not fit into a comment
predictedNO 2y

@ZhaoNan Ok, look up zero-knowledge proofs, construct one and we will send you statements to verify or disprove.

1y
Comment hidden

What is this?

What is Manifold?
Manifold is the world's largest social prediction market.
Get accurate real-time odds on politics, tech, sports, and more.
Win cash prizes for your predictions on our sweepstakes markets! Always free to play. No purchase necessary.
Are our predictions accurate?
Yes! Manifold is very well calibrated, with forecasts on average within 4 percentage points of the true probability. Our probabilities are created by users buying and selling shares of a market.
In the 2022 US midterm elections, we outperformed all other prediction market platforms and were in line with FiveThirtyEight’s performance. Many people who don't like trading still use Manifold to get reliable news.
How do I win cash prizes?
Manifold offers two market types: play money and sweepstakes.
All questions include a play money market which uses mana Ṁ and can't be cashed out.
Selected markets will have a sweepstakes toggle. These require sweepcash S to participate and winners can withdraw sweepcash as a cash prize. You can filter for sweepstakes markets on the browse page.
Redeem your sweepcash won from markets at
S1.00
→ $1.00
, minus a 5% fee.
Learn more.
© Manifold Markets, Inc.Terms + Mana-only TermsPrivacyRules