El problema de isomorfismo de grafos no es un problema P conocido ni un problema NP-completo conocido.
En realidad, parece flotar en algún punto intermedio.
Parece ocupar la única pequeña ventaja gris en los problemas naturales; y el único problema que es tan famoso como lo es el problema de la factorización prima (descomposición de factores primos).