3 ms·
> Babai’s new result says that solving graph isomorphism takes slightly longer than polynomial time – not quite placing it in P, but significantly shifting the
by 0xdeadbeefbabe 11y ago
> Babai’s new result says that solving graph isomorphism takes slightly longer than polynomial time – not quite placing it in P, but significantly shifting the needle for the first time.
What is the needle and how did it shift significantly for the first time?
Edit: They already knew it was in NP, but now they know it is not in P (or not quite in P)?
- andreasvc 11y agoAll of P is in NP. The result claims that it is close to P, when before it was probably expected to be much harder than P.
- poizan42 11y agoIf 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.