Is Graph Isomorphism NP-intermediate?
9
106
Ṁ229Ṁ190
2050
33%
chance
1D
1W
1M
ALL
It is known that GI is solvable in subexponential time n^polylog(n), which makes it unlikely to be NP-complete, unless the Exponential Time Hypothesis (ETH, see this market: https://manifold.markets/BoltonBailey/is-the-exponential-time-hypothesis?r=RmxvZmZpbm91) is wrong. If we believe in the ETH, GI could either be in P (see this market: https://manifold.markets/BoltonBailey/is-graph-isomorphism-in-p?r=RmxvZmZpbm91) or NP-intermediate:
Get Ṁ200 play money
Related questions
Is Graph Isomorphism NP-Complete?
7% chance
Is normal-play dots-and-boxes PSPACE-complete (YES) or in NP (NO)?
56% chance
P vs NP. Which of Impagliazzo's Five Worlds is true?
Is P vs NP solvable?
65% chance
Will P vs PSPACE be resolved before P vs NP?
59% chance
If P=NP is proven, will the first proof be constructive?
45% chance
Is Graph Isomorphism in P?
63% chance
What is the complexity theoretic status of P vs NP, ETH, and Graph Isomorphism?
Lehmer's totient problem: Is there a composite solution to φ(n) | n-1?
27% chance
Will P vs NP be resolved by 2043?
21% chance