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

дона для решения проблемы тождества слова для группы G Согласно полученной оценке в теореме I , а также ( 23 ) , (24), мы получаем оценку сигнализирующей функции времени,указанную в теореме. ТЕОРЕМА 4. Любая МТ для решения проблемы сопряженности слов в группе из класса К ( ^ ) имеет оценку сигнализирующей функции времени вида: t c m ^ h ) ^ Z 9 ( m .+h -)°+ l2389 ( rri+/b) +I8693h +(п г + + h ) -1- 3931S9709< п ь+ !ъ ? +-112.0i96299‘K т. + k f + + U 6 'H iS ¥6 l667 lm .+h ) +99-335'1912212 ISCm, + + k ) + 5 9 0 7 3 9 9 3 1 7 0 7 3 6 9 ( m +h ) + + W? 7959172 99 936 5 7 ( / +/г* + j ( rri - h * ) + + 96?Z ?5S1S9?099k88 (m +h ) + i l <m+/l)+- 6 +2 56869357990931O991. ДОКАЗАТЕЛЬСТВО. Применяем диагональный метод для получе­ ния нижней оценки сигнализирующей функции времени, используя последовательность групп (к), определенную ранее в § 2 . Для /г =1 рассмотрим группу (, . Пусть слова W W .eG и С( , & !*£>=■А. . ” ■ 1 I . Число операций циклического сокращения, примененных к словам Lt/ равно - 16 -