|
Математические основы информатики и программирования
О генерической сложности проблемы изоморфизма конечных полугрупп
А. Н. Рыбалов Институт математики им. С.Л. Соболева СО РАН, г. Омск
Аннотация:
Изучается генерическая сложность проблемы изоморфизма конечных полугрупп: по любым двум полугруппам одинакового порядка, заданным таблицами умножения, требуется определить, являются ли они изоморфными. К этой проблеме полиномиально сводится проблема изоморфизма конечных графов. Таким образом, проблема изоморфизма конечных полугрупп с вычислительной точки зрения не проще проблемы изоморфизма графов. Предлагается генерический полиномиальный алгоритм для проблемы изоморфизма конечных полугрупп. В его основе лежит характеризация почти всех конечных полугрупп как 3-нильпотентных полугрупп специального вида, а также полиномиальный алгоритм Боллобаша, решающий проблему изоморфизма для почти всех сильно разреженных графов.
Ключевые слова:
генерическая сложность, конечные полугруппы, изоморфизм.
Образец цитирования:
А. Н. Рыбалов, “О генерической сложности проблемы изоморфизма конечных полугрупп”, ПДМ. Приложение, 2021, № 14, 178–180
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma560 https://www.mathnet.ru/rus/pdma/y2021/i14/p178
|
|