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

C 2 J Щупд ( S c L u - p p Р Е ) On- <be.h i • ,ьп s a f f o r i t E m . . a n . с/ t h e co.yupa.cy />гьКтЛа 1 к . . J n -n . ., 998\1 1 9 - 1 3 p . [31 U p t o n . M .J .,2 a lc ste L ,n Y. J t y o r i Y A m Areal C o m n C e - X i i j . /Vcxs Y o r k e . CL.t 9 9 7 6 , 9 b. [41 Валиев М.К. О сложности проблемы тождества для конечно определенных групп.-Алгебра и л о г и к а ,т . 8 , № I (1969) с . 5-43. 1-5] Трахтенброт Б.А. Сложность алгоритмов и вычислений. - Новосибирск: НГУ, 1967. I й 1 L y n d o n d f Seh -U-/o/> Р . С о т £ щ - ^ ° r ±3- С y r o u . j o T ^ A e o / y B e r l i n - U ciclz££crji-M<vc. f o r } : S p r i n y e r t -1 9 7 ? C7'J Шатрова Н.П. Г В печати^ Верхняя оценка степени сложности алгоритма решения проблемы сопряженности дан одного класса групп. (87 Гриндяингер М.Д. ЪеСп. 's a t o o r i i k m . f o r Н е w o r d pro&tem. Comm . Pu.re dppP- M-cdn . , 73 , 69 -83 ( I 9 6 0 ). i Еёзьерхняй В.II . (Тула) РЕШЕНИЕ ПРОБЛЕШ ВХОЖДЕНИЯ В КЛАССЕ HNN - ГРУШ Рассмотрим конечно определенную группу С , выделим в ноя дне изоморфные подгруппы U, , U4 и фиксируем изоморфизм *Р такой, что (? (Ц ) U_, . Растроим HNN - расширение группы G , .яределяемое подгруппами Ц , & , и изоморфиз­ м у ' * ^ t - i d & \ r ' a t = ? ( a ) , t t 2 e u f > t ’ ’ ( i ) где буква t , не тинадлежащнл группе G , навивается пра­ вильной проходной буквой. ОИР’ДЕЛЕКИЕ I . Вуде говорить, что в группе G равре­ шала проблема пересечения классов с: .ясности конечно порожден­ ных подгрупп, если для любьк двух конечно i рожденных под­ групп Hf , Н 2 группы G и любого элемента и г е G существу­ ет алгоритм, позволяющий установить, пусто или нет пересече- - 20 -