О некоторых проблемах теории сложности вычислений, связанных с алгебрами отношений

Когерентной алгеброй называется матричная алгебра над полем комплексных чисел, содержащая единичную матрицу и матрицу, состоящую из единиц, и инвариантная относительно эрмитова сопряжения и аданарова умножения. Известно, что когерентная алгебра обладает стандартным линейным базисом, состоящим из $(0,1)$-матриц. Семейство отношений конечного множества определяет алгебру отношений, если все члены этого семейства могут быть получены объединениями отношений, матрицы смежности которых являются стандартным базисом некоторой когерентной алгебры. Алгебры отношений возникают при изучении проблемы изоморфизма графов.
В настоящей работе рассматриваются основные проблемы, связанные с оценкой сложности базовых алгоритмов для работы с алгебрами отношений. В их число входят алгоритмы вычисления стандартного базиса алгебры отношений, пересечения и объединения алгебр. Кроме того, описан подход к проблеме изоморфизма графов, основанный на концепции Шуровых алгебр отношений (соответствующие им когерентные алгебры являются централизаторными алгебрами групп перестановок). Статья завершается списком открытых проблем и обсуждением возможных направлений дальнейших исследований. Библ.: 18 назв.