On generic complexity of the isomorphism problem for finite semigroups.pdf Введение Понятие изоморфизма является одним из важнейших понятий в современной математике. Изоморфные объекты имеют одинаковые математические свойства, одинаковую математическую структуру. Это позволяет абстрагироваться от конкретных представителей этих объектов, однако это также порождает проблему изоморфизма: по двум конкретным представлениям определить, являются ли они изоморфными. Наиболее известной алгоритмической проблемой такого рода является проблема изоморфизма конечных графов. Несмотря на то, что эта проблема находится в центре внимания специалистов с 1970-х гг., до сих пор не найдено полиномиальных алгоритмов её решения. В то же время не доказана её NP-полнота. Таким образом, она может занимать промежуточное положение между проблемами из класса P и NP-полными проблемами. Проблема изоморфизма возникает для многих других конечных алгебраических объектов: групп, полугрупп, колец, полей, алгебр и т. д. Например, для конечных полей эта проблема решается тривиально: известно, что любые два конечных поля одинакового порядка изоморфны. Для конечных полугрупп ситуация гораздо сложнее. Простой алгоритм, который перебирает всевозможные биекции между полугруппами и проверяет, являются ли эти биекции изоморфизмами, работает за экспоненциальное время. Существуют ли полиномиальные алгоритмы для решения этой проблемы, неизвестно. В [1] доказано, что к этой проблеме полиномиально сводится проблема изоморфизма конечных графов. Таким образом, проблема изоморфизма конечных полугрупп с вычислительной точки зрения не проще проблемы изоморфизма конечных графов. В рамках генерического подхода [2] алгоритмическая проблема рассматривается не на всём множестве входов, а на некотором подмножестве «почти всех» входов. Такие входы образуют генерическое множество. Понятие «почти все» формализуется введением естественной меры на множестве входных данных. С точки зрения практики алгоритмы, решающие быстро проблему на генерическом множестве, так же хороши, как и быстрые алгоритмы для всех входов. В данной работе предлагается генерический полиномиальный алгоритм для проблемы изоморфизма конечных полугрупп. В его основе лежит характеризация почти всех конечных полугрупп как 3-нильпотентных полугрупп специального вида, установленная в [3], а также полиномиальный алгоритм Боллобаша, решающий проблему изоморфизма для почти всех сильно разреженных графов [4]. 1. Генерические алгоритмы Пусть I - некоторое множество входов. Для подмножества S С I определим последовательность относительных плотностей Pn(S) = туУ, n = 1 2 ^..^ |In| где In - множество входов размера n; Sn = SPlIn. Заметим, что pn(S) - это вероятность попасть в S при случайной и равновероятной генерации входов из In. Асимптотической плотностью множества S назовём верхний предел p(S) = lim pn (S). Множество S называется генерическим, если p(S) = 1, и пренебрежимым, если p(S) = 0. Очевидно, что S генерическое тогда и только тогда, когда его дополнение I \\ S пренебрежимо. Алгоритм A с множеством входов I и множеством выходов J U {?} (? G J) называется генерическим, если 1) A останавливается на всех входах из I ; 2) множество {x G I : A(x) = ?} является генерическим. Генерический алгоритм A вычисляет функцию f : I J, если Vх G 1 (A(x) = y G J) (f (x) = y). Ситуация A(x) = ? означает, что A не может вычислить функцию f на аргументе x. Но условие 2 гарантирует, что A корректно вычисляет f на почти всех входах (входах из генерического множества). Множество S Q I называется генерически разрешимым за полиномиальное время, если существует генерический полиномиальный алгоритм, вычисляющий его характеристическую функцию. 2. Проблема изоморфизма конечных полугрупп Для определённости будем рассматривать конечные полугруппы с элементами из множеств {1,2, . . . ,n}, n G N. Таблицей умножения конечной полугруппы S порядка n называется таблица n х n, в которой на месте (i,j) стоит результат произведения элементов i и j . Полугруппы S1 и S2 изоморфны, если существует биекция : S1 S2, такая, что для любых элементов a,b G S1 имеет место ^(ab) = ^(a)^(b). Биекция называется изоморфизмом. Проблема изоморфизма конечных полугрупп состоит в следующем: даны две конечные полугруппы S1 и S2 одинакового порядка, заданные таблицами умножения; определить, являются ли они изоморфными. Теорема 1. Проблема изоморфизма конечных полугрупп генерически разрешима за полиномиальное время.

Скачать электронную версию публикации