patternMinor
If graph isomorphism yields a polynomial time algorihtm
Viewed 0 times
algorihtmgraphpolynomialtimeyieldsisomorphism
Problem
Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes.
If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible implication it has or what can we possibly deduce?
Thanks for any explanation
If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible implication it has or what can we possibly deduce?
Thanks for any explanation
Solution
Nothing bad is known to happen if Graph Isomorphism can be solved in polynomial time; see this question on cstheory. On the other hand, problems in the complexity class GI will all have polynomial time algorithms.
Context
StackExchange Computer Science Q#56847, answer score: 2
Revisions (0)
No revisions yet.