Re:Quasi-Polynomial Algorithm for Graph Isomorphism
by Ar-Curunir on Wednesday November 04, 2015 @03:47PM
(#10509587)
Most real life instances of Graph Isomorphism are easily solved in polynomial time though...
[ Parent
| on HN ]
Re:Quasi-Polynomial Algorithm for Graph Isomorphism
by johncolanduoni on Wednesday November 04, 2015 @03:52PM
(#10509642)
Yes, they discussed in the comment section of the post that when theoretical computer science researchers have tried to find actual graphs which existing algorithms do not handle well, they had difficulties finding them outside of some very specific (and vanishingly small) classes.