What is the complexity theoretic status of P vs NP, ETH, and Graph Isomorphism?
Basic
4
Ṁ6092100
5%
P = NP
8%
P != NP, ETH false, GI in P
9%
P != NP, ETH false, GI NP-intermediate
1.6%
P != NP, ETH false, GI NP-complete
58%
ETH true, GI in P
18%
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
This question is managed and resolved by Manifold.
Get
1,000and
3.00
1,0003.00Related questions
Related questions
Is Graph Isomorphism in P?
61% chance
Is Graph Isomorphism NP-intermediate?
53% chance
Is P vs NP solvable?
65% chance
Will P vs PSPACE be resolved before P vs NP?
62% chance
Is Graph Isomorphism NP-Complete?
7% chance
Will geometric complexity theory solve P vs NP?
10% chance
Does P = NP?
9% chance
Can quantum computer check isomorphism of graphs in the described way?
3% chance
P vs NP. Which of Impagliazzo's Five Worlds is true?
When will someone successfully solve P vs NP?