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

О генерической сложности проблемы изоморфизма конечных полугрупп | Прикладная дискретная математика. 2021. № 51. DOI: 10.17223/20710410/51/6

Изучается генерическая сложность проблемы изоморфизма конечных полугрупп. В этой проблеме по любым двум полугруппам одинакового порядка, заданным таблицами умножения, требуется определить, являются ли они изоморфными. В. Н. Земляченко, Н. М. Корнеенко и Р. И. Тышкевич в 1982 г. доказали, что к этой проблеме полиномиально сводится проблема изоморфизма конечных графов - известная алгоритмическая проблема, которая активно изучается с 1970-х годов и для которой до сих пор неизвестно полиномиальных алгоритмов. Таким образом, проблема изоморфизма конечных полугрупп с вычислительной точки зрения не проще проблемы изоморфизма графов. Предлагается генерический полиномиальный алгоритм для проблемы изоморфизма конечных полугрупп. В его основе лежит характеризация почти всех конечных полугрупп как 3-нильпотентных полугрупп специального вида, установленная Д. Клейтманом, Б. Ротшильдом и Дж. Спенсером, а также полиномиальный алгоритм Боллобаша, решающий проблему изоморфизма для почти всех сильно разреженных графов.
  • Title О генерической сложности проблемы изоморфизма конечных полугрупп
  • Headline О генерической сложности проблемы изоморфизма конечных полугрупп
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 51
  • Date:
  • DOI 10.17223/20710410/51/6
Ключевые слова
генерическая сложность, конечные полугруппы, проблема изоморфизма
Авторы
Ссылки
Земляченко В. Н., Корнеенко Н. М., Тышкевич Р. И. Проблема изоморфизма графов // Записки научных семинаров ЛОМИ. 1982. Т. 118. С. 83-158.
Kapovich I., Miasnikov A, Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. V. 264. No. 2. P. 665-694.
Babai L., Erdos P, and Selkow S. Random graph isomorphism // SIAM J. Computing. 1980. V. 9. No. 3. P. 628-635.
Bollobas B. Distinguishing of vertices of random graphs // Ann. Discrete Math. 1982. V. 13. P. 33-50.
Kleitman D. J., Rothschild B. R., and Spencer J. H. The number of semigroups of order n // Proc. Amer. Math. Soc. 1976. V.55. No. 1. P.227-232.
О генерической сложности проблемы изоморфизма конечных полугрупп | Прикладная дискретная математика. 2021. № 51. DOI: 10.17223/20710410/51/6
О генерической сложности проблемы изоморфизма конечных полугрупп | Прикладная дискретная математика. 2021. № 51. DOI: 10.17223/20710410/51/6