I don&#x27;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&#x27;s still open).<p>Though extremely informative, there&#x27;s no reason that GI is polynomial (or pseudo polynomial) would give serious reason to believe that P is anywhere near NP.