|
Записки научных семинаров ПОМИ, 1992, том 202, страницы 116–134
(Mi znsl1727)
|
|
|
|
О некоторых проблемах теории сложности
вычислений, связанных с алгебрами отношений
И. Н. Пономаренко
Аннотация:
Когерентной алгеброй называется матричная алгебра над полем
комплексных чисел, содержащая единичную матрицу и матрицу, состоящую
из единиц, и инвариантная относительно эрмитова сопряжения
и аданарова умножения. Известно, что когерентная алгебра
обладает стандартным линейным базисом, состоящим из $(0,1)$-матриц.
Семейство отношений конечного множества определяет алгебру отношений,
если все члены этого семейства могут быть получены объединениями
отношений, матрицы смежности которых являются стандартным
базисом некоторой когерентной алгебры. Алгебры отношений возникают
при изучении проблемы изоморфизма графов.
В настоящей работе рассматриваются основные проблемы, связанные
с оценкой сложности базовых алгоритмов для работы с алгебрами
отношений. В их число входят алгоритмы вычисления стандартного
базиса алгебры отношений, пересечения и объединения алгебр.
Кроме того, описан подход к проблеме изоморфизма графов, основанный
на концепции Шуровых алгебр отношений (соответствующие им
когерентные алгебры являются централизаторными алгебрами групп
перестановок). Статья завершается списком открытых проблем и обсуждением возможных направлений дальнейших исследований.
Библ.: 18 назв.
Образец цитирования:
И. Н. Пономаренко, “О некоторых проблемах теории сложности
вычислений, связанных с алгебрами отношений”, Численные методы и вопросы организации вычислений. IX, Зап. научн. сем. ПОМИ, 202, Наука, СПб., 1992, 116–134; J. Math. Sci., 79:3 (1996), 1105–1114
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl1727 https://www.mathnet.ru/rus/znsl/v202/p116
|
Статистика просмотров: |
Страница аннотации: | 205 | PDF полного текста: | 79 |
|