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

верхнюю оценку согласно С77 и (4) t(tr v ') К (1 8 т ( г о,п-^)гЗъоггъ)((-г£гп*(т +m - ) i 3 z г п ) ^ ° О ^ £.( 18m . (Z 0+m-) 1 з zom . )+ З г0-1 п. i (18ш г z oi m ) 1 +3z0m -)K (6 ,Z 5 'C 18п г \ г 0+ +3 zoi - t l -f + 2 хо (. 1 8 гтъ съ0+гп)+ + З г ап г ') + 11, Z S ( i g m ! ‘( r 0+m.'>+ 3 t 0 ir 3 )+ 18 z ^ i-H z - *■> a - 7-)£op^n + C1 8 m \ z o* m ) 1 3 г дт г ) 8 d o ,8 7 6 C 1 8 m Vc z i-m .) + г З гоп гг) г+ 6 го ( 18m j zo+ m ) +3 7 вп ь ’) + Z9, i z s z * +3S,3?S(18rn.* * ( z + m ) +Ъгс пь ) + з г ,S z o+<?, w ) ( 5 ) Следовательно, из (3) и (5) мы получаем верхнюю оценку сигнализирующей функции времени для оценки степени сложности алгоритма решения проблемы .ождества слов в классе групп К( s '). t a n ) * К ( S 8 3 Z n i S+ 171 86 2 пг*1-1П967 m ! 3+ ( S 8 3 Z r 3+ о о О +2Э16 гв ) т .к 1 (3888 Z* +19* * Z J n z '-h СW 1 ?f+-918 2 * 1 -6 9 8 - ~18z ) m r°-h(Ш г г 1-1896 7 ) m f i r i 6 8 г 3+ 9 ? гz s )i7 t+ 2 .16Z пъ-*- О о О О о + (87 z j *-21б г„)/тг 6+(S* г* -1 8 )т * 1 (6 9 Zgi-18Z? ) m r+ (9 z3- 3 z o-+ iffir r i + m + ( 3 z * - i)m .) fo c £ n + (9 с /п ^У£ у гп -) * * ( 6 ) ТЕОРЕМА 2 . Для любой МТ сигнализирующая функция времени для решения проблемы тождества слов в классе групп имеет оценку t o n ) » ^ ~ <.S 6 t m ? iT T 7 8 m s i / * ^ + + 8S9Zm * 1- 3 m s + 2 T o n . *i f f б £ ^ +9 . Здесь m _ длина испытуемого слова рассматриваемой группы в образующих символах этой группы ДОКАЗАТЕЛЬСТВО. Определим рекурсивную последовательность групп из клас а Кс%) . Пусть G 0 = <C L 1 ; c t * > - 8 -