Dwie macierze powiązane permutacją

Jaka jest złożoność obliczeniowa następującego problemu:

dane dwie złożone macierzy i sprawdzają, czy istnieje macierz permutacji taka, że: B P B = P P T$n\times n$$A$$B$$P$

Jeśli to pomoże, można założyć, że i są pustelnikami (lub nawet, że i są rzeczywiste i symetryczne).B A $A$$B$$A$$B$

Uwagi:

Problem polega na sprawdzeniu, czy dwa zestawy wektorów są powiązane przez obrót jednostkowy, zobacz Zestawy wektorów powiązane przez obrót - MathOverflow . W tym kontekście i są ich matrycami Gramiana .$A$$B$

Problem jest co najmniej tak trudny jak problem izomorfizmu graficznego - weź i jako macierze przylegania.$A$$B$

Jest to równoważne z podjęciem decyzji, czy dwa podane multigrafy (lub wykresy oznaczone krawędziami) są izomorficzne, czy nie, co jest znane jako równoważne zwykłemu problemowi z izomorfizmem grafowym.