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

+-г0Я9711О+Л56Cn.+'O*8* 193 ¥4f 9632 ( П П ) i-9 6 ^ f'S £ i'ГбГ/т.4}* -Г9 6 S~&SfGCn-+lj*-r-29SS93+ ( n +*) + 2 * * 2 ?•*<* C” -+ 1 ) + s e if $ ■1559692 c n + f) + 33 "6 (n -> i) + l$ 0 S (n .+ i)+ 2 ‘/(n .+ i)+ ts- (29; Согласно полученным оценки,! ( 2 8 ) , ( 29 ) , следует, что лвэбая МТ реализующая алгоритм решения проблемы сопряженности д -д после­ довательности групп к имеет сигнализирующие функции времени находящиеся в соотношении В 0 £ ± ^ ( т . , к ) ± . . . < - £ ^ (т ., к .) 6 . . . ( 30) i { т , к ) - сигнализирующая функция времени для группы G 1 , t ( т , к ) - сигнализирующая функция времени для группы < v Из полученной последовательности неравенств (30) следует утверждение теоремы. Аналогично тому, как мы показали, что группы (У* , <*г имеют оптимальные оценки степени сложности алгоритма решения проблемы тождества слов, можно п о к азать, что группы <5?, Gz имеют оптимальные оценки и для решения проблемы сопряженности слов. i З А К Л Ю Ч Е Н И Е . Полученные оценки степени сложности алгоритма решения ' проблемы тождества слов и сопряженности для класса групп К ( $ ) являются закономерными. Действительно в классе /<(%) существуют группы СЦЛ , <5, для которых оценки сягнализ" та­ ющей функции времени являются оптимальными и аосимптотически по порядку совпадают о нижней оценкой сигнализирующей функ­ ции времени для класса * ( $ ) . СПИСОК ИСПОЛЬЗОВАННОЙ литератуш Ш Ливдон ( L y n d o n f t . с . ) O n Ъ е к п 'з a C f o n t k u m . J loJ .L -J .nn .., 166 , 2 0 8 - Z 2 S . ■ 19 -