Is Graph Isomorphism in P?
➕
Plus
17
Ṁ479
3000
61%
chance

This market will resolve once a widely-accepted proof exists that the graph isomorphism problem is or is not in P.

Get
Ṁ1,000
and
S3.00
Sort by:

Wouldn't a "no" resolution require a proof that P != NP?

@placebo_username If GI were known to be NP complete then this would follow, but this is not known. See this question for more detailed alternatives. (Edit, actually, indeed, it follows even without knowing GI to be NP Complete)

@BoltonBailey That's not true. Graph isomorphism is known to be in NP. If P = NP, then graph isomorphism must be in P. The contrapositive: if graph isomorphism is not in P, then P != NP.

@placebo_username Graph Isomorphism is known to be in NP. But it is not known to be NP complete. If GI were NP complete, then a polynomial time algorithm for it would imply P = NP, and a proof that no polynomial time algorithm existed for it would imply P != NP.

@BoltonBailey I suppose you are correct that if GI were shown not to be in P, then that would be enough to show P != NP, even if the completeness weren't known.

Could be

© Manifold Markets, Inc.Terms + Mana-only TermsPrivacyRules