The major implication I care about concerns the feasibility of A.I., specifically because I believe "analogy finding" and knowledge reuse to rest on tractable sollutions to the subgraph isomorphism problem.

You could build an AI which restricts itself to solving small cases of the problem, finding "petty" analogies, and growing more complex ones ontop. Any (computationally efficient) algorithm which could find isomorphisms for larger problems directly in polynomial time would blow a "bottom up" analogy finder out of orbit.

Though ofcourse if anyone reading could point out a method for finding subgraph isomorphisms on large graphs that is "good enough" by some standard, I'll be happy to learn of it :)