- The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate. - This problem is a special case of the subgraph isomorphism problem,which asks whether a given graph G contains a subgraph that is isomorphic to another given graph H; this problem is known to be NP-complete. - Since the graph isomorphism problem is neither known to be NP-complete nor known to be tractable, researchers have sought to gain insight into the problem by defining a new class GI, the set of problems with a polynomial-time Turing reduction to the graph isomorphism problem.