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

2 (n,+-ifi 3п г"* 108пгя: 9?2n i?i- -Urn- 321m. 1-2 ?m пь + + 1 )1 -3/n r+3*sr>. *+9m ' *■ o, S/r>, (17) Следовательно, сигнализирующая функция времени любой ЫТ, при­ маненной к слову ^/ £ ^п. . имоет оценку i Cm) ~> Z (гъ-+ 1 * ( 3 сп *V logm f i-972 m ?+ ISm?+ 329 r n 6 + g ?/тг + ft. + r i rn'*'h +3 m X+S+m.‘, i- QmZ+ -M . Мы получаем, что в классе К ( s ') существует последователь­ ность групп { йгд. ] , сигнализирующие функции которой любой МТ для решения проблемы тождества слов находятся в соотноше­ нии 29m ,°i-H9ni i-??*b/7t-t-?99пгf*2SS>2m**3rnsi-Z?o ть + 9 ^ -n t + + i ~ m +9 & Д C m ) ^ ^ T ^ C m ) Из этой последовательности неравенств следует доказательство теоремы. Принимая во внимание теоремы I и 2 , мы получаем оценку степени сложности алгоритма решения проблемы тождества сл о в 1 для класса конечно определенных групп, множество определя­ ющих слов которого оимметризованно и удовлетворяет условию ■ ( 6 ) . Сигнализирующая функция времени имеет ассимптотическиеt оценки такого вида: Z b r n 0*- 0 - ( т ° ) K ( S S 3 Z m 1s+ 1 ?ц?6 г О * 19tf967- о Ш з г г0?/п'г-е (3888г*+ 199?7о )т + (М 9 7 * + i-99Z730 -C8r+ 69g)m !0+ (<296 % + Z * ) m \ 6Z i6rem i-(2 i6 x * i-2 ? 4 ) пт?+CS9 гД lg)m f + (S^ \ m i ) т 9+ +( n l - 3 x + 2 ) m i + > r ,\( 3 z 4 1 ) ъ ) { 0 £ л : v- a (r r lSU ? * n ) , - I I -