Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T...
by lmkg on Thursday November 12, 2015 @04:05PM
(#10556119)
> NAUTY (and SAUCY) were good practical implementations
> that found solutions efficiently (except for some
> harder class of graphs, maybe).
There are good practical implementations of SAT solvers as well (except degenerate cases), even though SAT is the canonical NP-Complete problem.
Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T...
by abetusk on Thursday November 12, 2015 @05:24PM
(#10556581)
Fair enough, though I think the problem space is substantially different (though I didn't mention it above). It's much easier to make (random) 3-SAT difficult instances whereas for GI you needed highly structured graphs. Apparently Johnson graphs were one of the classes of graphs that caused people problems in GI.
Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T...
by wolfgke on Friday November 13, 2015 @10:28AM
(#10560310)
There are other NP-complete problems, where really hard instances are a lot more rare.
Re:A Quasipolynomial Time Algorithm for Graph Isomorphism: T...
by erik on Thursday November 12, 2015 @04:17PM
(#10556197)
I didn't think that GI was known to be in co-NP.
Though extremely informative, there's no reason that GI is polynomial (or pseudo polynomial) would give serious reason to believe that P is anywhere near NP.