Apa kompleksitas komputasi dari masalah berikut:
diberikan dua kompleks matriks A dan B cek jika ada permutasi matriks P sehingga: B = P A P T .
Jika itu membantu, orang dapat berasumsi bahwa dan B adalah hermitian (atau bahkan A dan B itu nyata dan simetris).
Catatan:
Masalahnya berasal dari memeriksa apakah dua set vektor terkait oleh rotasi kesatuan, lihat Set vektor terkait oleh rotasi - MathOverflow . Dalam konteks itu, dan B adalah matriks Gramian mereka .
Masalahnya setidaknya sama sulitnya dengan masalah grafik isomorfisme - ambil dan B sebagai matriks kedekatan.