4 ms·
I don't know why you would think this. There was strong empirical evidence (in my opinion) for thinking Graph Isomorphism was easy. NAUTY (and SAUCY) were goo
by abetusk 11y ago
I don't know why you would think this. There was strong empirical evidence (in my opinion) for thinking Graph Isomorphism was easy. NAUTY (and SAUCY) were good practical implementations that found solutions efficiently (except for some harder class of graphs, maybe). GI was known to be in NP and co-NP which is usually a red flag that the problem is not NP-Complete. For example, linear programming, integer polynomial factorization and primality testing were all in this NP and co-NP region (also discrete logarithm but that's still open).
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.
- lmkg 11y ago> 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.
- abetusk 11y agoFair 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.
- wolfgke 11y agoThere are other NP-complete problems, where really hard instances are a lot more rare.
- erik 11y agoI didn't think that GI was known to be in co-NP.
- abetusk 11y agoScott Aaronson's answer on MO indicates it was known under "suitable popular derandomization assumptions" [1]. [1] http://mathoverflow.net/a/32312 http://mathoverflow.net/a/32312