Какова вычислительная сложность следующей задачи:
с учетом двух комплексных матриц A и B проверить, есть ли матрица перестановок Р таким образом, что: В = Р Р Т .
Если это помогает, можно предположить, что и B эрмитовы (или даже что A и B действительные и симметричные).
Примечания:
Проблема связана с проверкой, связаны ли два набора векторов унитарным вращением, см. Наборы векторов, связанных вращением - MathOverflow . В этом контексте и В являются грамианскими матрицами .
Задача, по крайней мере, такая же сложная, как и проблема изоморфизма графов - возьмите и B в качестве матриц смежности.