HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

If graph isomorphism yields a polynomial time algorihtm

Submitted by: @import:stackexchange-cs··
0
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

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.