What is the complexity theoretic status of P vs NP, ETH, and Graph Isomorphism?
4
64
Ṁ587Ṁ250
2100
1D
1W
1M
ALL
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 Ṁ600 play money
Related questions
Is Graph Isomorphism in P?
63% chance
Will P vs NP be resolved before man lands on Mars?
27% chance
Is Graph Isomorphism NP-intermediate?
33% chance
Will P vs NP be resolved by 2043?
21% chance
Is P vs NP solvable?
65% chance
Is normal-play dots-and-boxes PSPACE-complete (YES) or in NP (NO)?
56% chance
If P=NP is proven, will the first proof be constructive?
47% chance
Are any Millennium Prize problems undecidable/unprovable/unsolvable?
23% chance
Is Integer Factorization in P?
19% chance