What is the complexity theoretic status of P vs NP, ETH, and Graph Isomorphism?
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.00Sort by:
This market was mainly created for arbitrage with:
Plus
Is Graph Isomorphism NP-Complete?7% chance
Plus
Does P = NP?6% chance
Plus
Is Graph Isomorphism in P?51% chance
What is this?
What is Manifold?
Manifold is the world's largest social prediction market.
Get accurate real-time odds on politics, tech, sports, and more.
Win cash prizes for your predictions on our sweepstakes markets! Always free to play. No purchase necessary.
Are our predictions accurate?
Yes! Manifold is very well calibrated, with forecasts on average within 4 percentage points of the true probability. Our probabilities are created by users buying and selling shares of a market.
In the 2022 US midterm elections, we outperformed all other prediction market platforms and were in line with FiveThirtyEight’s performance. Many people who don't like trading still use Manifold to get reliable news.
How do I win cash prizes?
Manifold offers two market types: play money and sweepstakes.
All questions include a play money market which uses mana and can't be cashed out.
and can't be cashed out.Selected markets will have a sweepstakes toggle. These require sweepcash to participate and winners can withdraw sweepcash as a cash prize. You can filter for sweepstakes markets on the browse page.
to participate and winners can withdraw sweepcash as a cash prize. You can filter for sweepstakes markets on the browse page.Redeem your sweepcash won from markets at 1.00 → $1.00, minus a 5% fee.
Learn more.1.00Related questions
What is this?
What is Manifold?
Manifold is the world's largest social prediction market.
Get accurate real-time odds on politics, tech, sports, and more.
Win cash prizes for your predictions on our sweepstakes markets! Always free to play. No purchase necessary.
Are our predictions accurate?
Yes! Manifold is very well calibrated, with forecasts on average within 4 percentage points of the true probability. Our probabilities are created by users buying and selling shares of a market.
In the 2022 US midterm elections, we outperformed all other prediction market platforms and were in line with FiveThirtyEight’s performance. Many people who don't like trading still use Manifold to get reliable news.
How do I win cash prizes?
Manifold offers two market types: play money and sweepstakes.
All questions include a play money market which uses mana and can't be cashed out.
and can't be cashed out.Selected markets will have a sweepstakes toggle. These require sweepcash to participate and winners can withdraw sweepcash as a cash prize. You can filter for sweepstakes markets on the browse page.
to participate and winners can withdraw sweepcash as a cash prize. You can filter for sweepstakes markets on the browse page.Redeem your sweepcash won from markets at 1.00 → $1.00, minus a 5% fee.
Learn more.1.00Related 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?