What is the complexity theoretic status of P vs NP, ETH, and Graph Isomorphism?
Basic
4
Ṁ587
2100
6%
P = NP
10%
P != NP, ETH false, GI in P
8%
P != NP, ETH false, GI NP-intermediate
1.4%
P != NP, ETH false, GI NP-complete
62%
ETH true, GI in P
14%
ETH true, GI NP-intermediate

The Graph Isomorphism problem (GI) was shown by Babai to be subexponential. Therefore, the possibility that GI is NP-complete is inconsistent with the exponential time hypothesis

The answers provide the remaining mutually exclusive possibilities for the questions of whether:

  • P = NP

  • ETH is true

  • GI is NP-Complete

  • GI in P

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

This market was mainly created for arbitrage with:

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