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
Does P = NP?
6% chance
Will geometric complexity theory solve P vs NP?
10% chance
Is Graph Isomorphism in P?
51% chance
Is Graph Isomorphism NP-Complete?
7% chance
Is Graph Isomorphism NP-intermediate?
44% chance
Is P vs NP solvable?
63% chance
Can quantum computer check isomorphism of graphs in the described way?
3% chance
Will P vs PSPACE be resolved before P vs NP?
71% chance
When will someone successfully solve P vs NP?
P vs NP. Which of Impagliazzo's Five Worlds is true?