3 ms·
If it was proven that it's not in P then we would have shown that P!=NP which would be HUGE. No, this is "merely" finding a more efficient algorithm for a prob
by poizan42 11y ago
If it was proven that it's not in P then we would have shown that P!=NP which would be HUGE.
No, this is "merely" finding a more efficient algorithm for a problem which we still don't know exactly where belongs. From a complexity theoretical viewpoint nothing is changed. It's still possible that graph isomorphism is in P.
Now if graph isomorphism is shown to be NP-complete then this result would imply that every problem in NP can be solved in sub-exponential time which would have huge practical consequences.