Прикладная дискретная математика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2021, номер 51, страницы 120–128 (Mi pdm734)  

Математические основы информатики и программирования

О генерической сложности проблемы изоморфизма конечных полугрупп

А. Н. Рыбалов

Институт математики им. С. Л. Соболева СО РАН, г. Омск, Россия

Аннотация: Изучается генерическая сложность проблемы изоморфизма конечных полугрупп. В этой проблеме по любым двум полугруппам одинакового порядка, заданным таблицами умножения, требуется определить, являются ли они изоморфными. В. Н. Земляченко, Н. М. Корнеенко и Р. И. Тышкевич в 1982 г. доказали, что к этой проблеме полиномиально сводится проблема изоморфизма конечных графов — известная алгоритмическая проблема, которая активно изучается с 1970-х годов и для которой до сих пор неизвестно полиномиальных алгоритмов. Таким образом, проблема изоморфизма конечных полугрупп с вычислительной точки зрения не проще проблемы изоморфизма графов. Предлагается генерический полиномиальный алгоритм для проблемы изоморфизма конечных полугрупп. В его основе лежит характеризация почти всех конечных полугрупп как 3-нильпотентных полугрупп специального вида, установленная Д. Клейтманом, Б. Ротшильдом и Дж. Спенсером, а также полиномиальный алгоритм Боллобаша, решающий проблему изоморфизма для почти всех сильно разреженных графов.

Ключевые слова: генерическая сложность, конечные полугруппы, проблема изоморфизма.

Финансовая поддержка Номер гранта
Российская академия наук - Федеральное агентство научных организаций I.1.1.4, проект № 0314-2019-0004
Исследование поддержано Программой фундаментальных научных исследований СО РАН I.1.1.4, проект № 0314-2019-0004.


DOI: https://doi.org/10.17223/20710410/51/6

Полный текст: PDF файл (663 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 510.52

Образец цитирования: А. Н. Рыбалов, “О генерической сложности проблемы изоморфизма конечных полугрупп”, ПДМ, 2021, № 51, 120–128

Цитирование в формате AMSBIB
\RBibitem{Ryb21}
\by А.~Н.~Рыбалов
\paper О генерической сложности проблемы изоморфизма конечных полугрупп
\jour ПДМ
\yr 2021
\issue 51
\pages 120--128
\mathnet{http://mi.mathnet.ru/pdm734}
\crossref{https://doi.org/10.17223/20710410/51/6}
\elib{https://elibrary.ru/item.asp?id=44878079}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm734
  • http://mi.mathnet.ru/rus/pdm/y2021/i1/p120

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:42
    Полный текст:22
    Литература:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2022