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

времени с оценкой ^Глч) ^ 2 ‘n 7 i ° + 8 6 ^ n i 9+ f f f g f r J ■+■ f 4 t m ? + 2 . 9 9 2 З т 3 +2?0/7i>+9 y/nf'-i- ^ f / n +9 ( I D Для tb =2 рассматриваем группу (X, , Приметаем алгоритм Дэна к адову ifc'eftj и £ (\х /)^т , . Число операций в результате применения алгоритма Дэна равно 7 , 5 п ъ -ь 1 Z, 5" ллг ( 12 ) В группе строим слова вида ( 8 ) . Применяем алгоритм Дэна к этому адову. Число операций будет равно 5Чпг°+ 1Н 96пг-гзг 4 т. + &згт?-<-Зт-1-940п1?+9тг ( 13 ) Согласно (12) и (1 3 ), алгоритм решения проблемы тождества слов в группе ft, содержит число операций равное 5 l n 0 i-f9t4rri+ 1 ?ш п£+ зг< /пг+5S3Zm+3n+Srtfri\w,5/7lH£'Sni+&. (14) , Сигнализирующая функция времени в группе ft) для любой МТ, реализующей алгоритм решения проблемы тождества слов, согласно (14) имеет оценку £ ( т ) > 5 ¥т °+ 19Ит?+1?¥ $6 /п?*-Э 2 ¥т fsSSs& /r t+ 3 ms *т L £ +5 4 0m + /i о. S ' m t - -/г, $ m +/д Рассмотрим группу Gn для произвольного п. . Пусть 1л/e G ^ и -C(W> . Применяем алгоритм Дэна к слову 1л/ . Число опе­ раций будет равно [ f ] + г Ovnfl f]L f ] 6 Z(n+<f(%*+ f n - n ) (I5) Строим в группе Gn слова вида ( 8 ) . Применяем алгоритм Дэна к построенному адову вида ( 8 ) . Число операций, примененных к это чу слову, равно ZlrL-rrfi irrL°t 1oSrrt*372rr^+ 18/71+32¥ni г г ш ^ ^ Согласно (1 5 ), (1£), алгоритм решечшя проблемы тождества для группы f t содеришт число операций.равное - 10 -