Dos matrices relacionadas por una permutación - complejidad

¿Cuál es la complejidad computacional del siguiente problema:

dados dos complejos matrices y verifique si hay una matriz de permutación tal que: $n\times n$$A$$B$$P$

Si ayuda, uno puede suponer que y son hermitianos (o incluso que y son reales y simétricos).$A$$B$$A$$B$

Notas:

El problema surge de verificar si dos conjuntos de vectores están relacionados por una rotación unitaria, consulte Conjuntos de vectores relacionados por una rotación: MathOverflow . En ese contexto, y son sus matrices de Gramian .$A$$B$

El problema es al menos tan difícil como el problema del isomorfismo gráfico : tome y como matrices de adyacencia.$A$$B$

Es equivalente a decidir si dos multigrafos dados (o gráficos con etiqueta de borde) son isomorfos o no, lo que se sabe que es equivalente al problema de isomorfismo gráfico habitual.