АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1981 г.

i(m .) & 2л гг +2.92 m. Применяем алгоритм Дэна к слову вида ( 8 ) и , учитывая оценки (8 ) и ( 20 ) , получаем оценку числа тактов алгоритма решения проблемы тождества слов для группы <5, t ( m .) 6 7 2 т . % 2 3 9 2 т ? +23329/п ? + 932т*+ т 6+ (20) + 17-52 m f + 3 2 1 3 9 л г V 5 2 5 9 т .г +292 т. ( 21 ) Сравнивая оценки ( I I ) и ( 21 ) , мы получаем ассимптотическое равенство для сигнализирующей функции времени в группе : t ( m ) x m 1Q. § 4. Оценка степени сложности алгоритма решения проблемы сопряженности в классе групп : Из алгоритма Щуппа получаем, что, если слова ^ , 1Х-г сопряжены в группе Q=< а--, , л г.> ■■■ » а п. » * 1 » • • ' ’ ** > из класса К ( у ) , то существует хотя бы одно слово T - i J z . . ■£р такое, что Т ~ 1 k ; Т \У г 1 ~ 1 , ^ ; 7 -п ъ а .х . l ( R - ) : <£• - подслово определяющего слова . Длина ° 1 H i £К *■ 7 L слова ' Т в образующих символах группы G не больше, чем Y - ТЕОРЕМА 3. Пусть G -произвольная группа из класса Л 7 ^ ). Тогда верхняя оценка сигнализирующей функции времени МТ для решения проблемы сопряженности группы 6 г имеет вид: А ) + <(5832(пг + А )5+0 9 9 6 го (5 *.+<)(m +А.Г+17996го (3 3 к*г+ 19?0+ +1'Хт+к)Ъ+932з (Z7iOKZl + 1638< \z +239K7 бТ^+ЗЗП+А)'+1Н9? ( W S k ?3+ ° О О v о в о +3236К*Z*+702,К*?*+367** 18 к 7 * 2-1 +7)(m+A)+(1?S139966zs'+19S13996K %f+ О О о о О о ° * 50038S6K 2 ■‘'+399912 К*+19г95б/г 3 +15211JK73 +21389*7 *+19997*+992 73+ ° О о о О о +698 - Ц т ^ т +А) +(29189160 л вг ‘ +399959992* A S +125О9к+0к у7 А 1283990 к \‘+ о о о ' 0 +691SZOK 7а +г 13890К г*, Юб920**7A 199Ч0*7о +9720*7^+6990*7^- 180 *7*+ о - 13 -