Алгоритмические проблемы для многообразий групп Анохин, Михаил Игоревич

Введение к работе

Актуальіі_ос?ь текн. Алгоряг-ляческиэ проблемы теоряя групп подвергались нятексявнсму язучеіпп) п тачание долгого зрзкеня (см., напрамзр, обзоры [1, 7; 2, гл. 1; 3]). Однако этя про-бдэкы псслэдоваллсь в оснозксм для. груші, заданных конечнім числом порохдаксях з огтрздал.сшях соотнсяошіЗ (конечно опреде-лонннх (к. о.) групп), а таг-стэ для протпволъннх конечно порождению: групп. Коц&чно порожденные свободные группы конечно Оа-яярустлух многоеЗразші бо многих случаях ко являются к. о., но для них суцостзует остастБвнкнЗ способ заддняя конечным числом порездандях з тождественных соотношений (т. э. базисом TOS-дестз соотпотствупного многообразия). Диссертация большей часты) посвяцона "зучензв атгорптмичосклх проблем для групп, за-данлнх конечным чделем пороїдйпцях з толдэстаєнних соотпосеняЗ (конечно оадангшх тоддествачя (к. я. т.) групп), а тага» для групп, я. о. т. в некотором многообразия я для конечно базяру-зкіх (к. б.) многообразий групп. В этом направлении мезнэ от-

1. Г. А. Нсскоз, Б. Н. Рамзсленниксв, В. А. Рсманькоа. Бесконечно групнн // Ктогя науки а так?. Алгебра. Топология. Гескэтряя, ч. 17, с. 65-157. - П.: ВИНИТИ. 1979.

2. 3. К. Реиэсленпзкоз, В. А. Романьков. Теоретикс-модельнна а алгоритиэтвекпэ вопроси теорзаг групп // Итога науки п їахя. Алгебра. Топологзя. Геометрия, т. 21, с. 3-79. -И.: ВИНИТИ. 1383.

3. Л. А. Еокуть, Г. П. Кукпн. Нзразрегакмнв алгорзтмячэсжяе ароблег-Я для полугрупп, групп з г.олац // Итоги наукп и техн. Алгэбра. Топология. Геометрия, т. 25, с. 3-66. -Е.:-ВИНИТИ, 1S37.

метать известный результат D. Г. Клеймана [4~] о существовании 2-порожденной 6 7-ступанио разрешимой к. з. т. группы, в которой проблема равенства неразрешима. Из существования такой группы следует существование тождества, проблема распознавания следствий которого алгоритмически неразрешима. В 4] доказало также существование такого тождества Ы = l , что на существует алгоритма, выясняющего по произвольному тождеству, является лн U = і ого следствием. Позднее С. В. Айвазян [53, используя метод Клеймана, построил ^ 5-ступенно разрешимую 2-порозденную к. з. т. группу с неразрешимой проблемой равенства.

В диссертация изучается следувдив алгоритмические проблемы.

4. Пусть ! і - некоторый класс коночных заданий груїш, а г - некоторое абстрактное теоретико-групповое свойство. Существует .га алгоритм, опрвделялцик по произвольному задшшв из і і , обладает ли соответствующая группа свойством г ? Другпмя словаки, распознаваемо ли свойство г в классе групп, определявши заданиями из l I ?

5. Пусть D - некоторый класс конечных систем тождеств, a (^/ - некоторое свойство многообразий групп. Существует ли алгоритм, вняснявщий по произвольной системе аз

D , обладает ле определяемое е8 многообразна свойствен Ц/ ? Другими словаыа, распознаваемо ле свойство ( в

4. D. Г. Клейман. О тождествах в группах // Тр. Иоск. иат. о-ва, 1982, т. 44, с. 62-108.

5. С. В. Айвазян. Об одной проблема А.-К. Мальцева // Сиб. мат. а., 1988, т. 29, Ш 6, с. 3-11.

клессз кногообразнй, опрэделяэмнх «гстеиама из D ?

.3. Пусть (^, - некоторнй класс групп о заданными коночными пля счотккмя системами пороздаших, a ^ - некоторнй вад сводимости. Какой шгет бнть 1 -степень неразрешс-иости проблоиа равенства груши аз О ? (Во ыяогах случаях

*-стенань пробломи равенства конечно порозденной группа не завзсет от внбора коночной система зорсддшестх.)

6. Построить группу, в которой разрешала пробхвиа равенства, но норазроштаа проблема тоздественннх соотнозеняЙ (т. е. многэство всех тоддеств, нстшшнх в ной, нерекурсивно)_t обла-дгззуя хоросшма сзоЗстзама.

7. Пусть І і - некоторцЗ класс конечных задавай групп, з которых разрзапма проблема равенства. Существует ля вдиннй (равномерный) алгсрзтн, рэаагаиЗ проблему равенства по произвольному эаданЕО пз I I ?

8. Пусть I - некоторый класс конечных заданий групп,

а I - цнозоство всох залаяли из I , опродалящах группа с разрезішоа проблемой равенства. Какова адгорятмяческая прпрода шогаства I ? В частности, входя? зз оно в варар-хпв Кляш - Мостсвского (арзфуатическуэ zepapxzs). я вела входят, то где ого шсто а этой иерархия?

Сформуляруеи вкратце некоторые резухьтати по этан про-

блеиаа. Через UL мз обозначаем многообразие всех ^ ҐІ-ступенно разрэпяких групп (т. о. П-э степень иногообразяя зсэх аболевых групп

1. Произвольное карковсков (в частвостк, натрявяадьвое наследственное) свойство нораспозпавазио в классе всех в. о.

. 4 -

групп (теорема Адяна - Рабина; ои. [6, теорема 4.1 гл. 1*3). Полнцккличность, еверхразрвшимость» нильпотентность, абелевость, Цикличность, конечность, тривиальность распознаваомн в

классе всех раэршшлых к. о., а также к. о. в Uu груш С?J. Тривиальность и периодичность в классе всех к. а. т. груші, а такеє абелевость, нильпотентность к конечность в классе разрешимых к. в* т. групп распознававши

2. Тривиальность и периодичность в классе всех к. б. многообразий група, а їеїзш абелевость н кросс-ЭЕОсть (поразда-еыость конечной группой; си. 18, е. 231-2323) в классе разроак-мых к. б. многообразий распознаваем.

3. Стевзкьэ ЕзразрзЕк^оз-хх проблемы равенства к. о. групші ыо&эт быть любая рокурсЕьно порвчаолнмая it-стеаєаь С9, 10]. Для лмбого їаохйства ' А натуральних чесол cyrsae-

6. Р. Линдой, II. Щупп. Комбинаторная творїія групп, - Ы. *. Нір, 1980.

7. О-. Bautnsian,, f.B. Catmondo, C.F.NiUeilll .. Some ищпш lit pxopetiles ot sohdh utoups// ' Ш. Z./19M, Ы..Ш, / 3, S. 2S9-295.

8. D. А. Бахтуран, А/ Ю. Ольпааскай. Тоадества // Алгвбра-2. Итоги науки и техн. Совр. пробл. дат. унд. направл., т. 18, с. 117-240. - Ш.: ВИШНИ, 1988.

9. U. К. Валявв. О сложности проблемы тождества для конечно опроделаннш. групп // Алгебра к лотка, 1969, т. 8, # 1, с. 5-43. . .

ю. 2). J. Collins. Тгиік-ійііе debtees and ike Boo^e noups // Amu'Halh., 1971, v. 94, Ji3, _P. 392-336.

твувт 2-порождоппая группа

G 01 такая, что М

1-сзс.щпло к проблема равенства п \т я проблока равенства н Ст- С -сводила к 1 I .В частности, степенью неразрешимости проблеми рьвокства 2-порождешюй группы пз \)1 ксдот бкть любая С-стопэиь ll, 12J и любая наслздстгекБая hl~ стопзнь, отличаая ст і Ю 5 П13.?. Существует рэкурсстно па-рэчкелтая >т.-ст8понь, d которой нэт проблемы равонстза пикакс! грушш C14J.

4. Суцостзузт 3-порслдэнная (п дала 2-породденная) группа из Ц1> , в которой разрэпяка проблема равонстза, ко нэразрззиа проблема тодцостзенных соотношений [4J.

5. Существует разно^эрниЗ алгоритм, решащлн проблем равзнстза по произвольно?^ задашп) конэчвжл числом породдавдих я опрэделяпцях и тождественных соогношокиЗ фяпитно аппроксимируемой группы С6, та орана 4.6 гл. IV 3 . Такого алгоритма на существует для всех заданий конечным числом пореадащих и

11. 0. В. Бвлэградак. Об алгебраически замкнутых группах // Алгебра я логика, 1974, т. 13, Я 3, с. 239-255.

12. М. Ііеаігг. Griuppen mil Voiaesckuehnern, ШІриМм I/Walk. Ann,., me, U. 2І9, i/ii, S. HZ-5L.

13. 0. В. Евлоградек. Об ІТІ-стопонях проблеми тоядоства слог // Слб. кат. ж., 1978, т. 19, Л б, с. 1232-1236.

і4. М. ІіцНг. Еіґі teKursLV au^zahlfotet Ш-GW, Лег кіс№ zun Wobtptoiuwi гіп&г ігирре, й&когі//Z. math. Loaic md ыЛ Hath, №, Bl 21, № 2, $ЖМ

опрэдзллзщюс соотношений групп с разроЕПімой проблемой равенства и даже для некоторого рекурсивно перочислимого множества таких заданий j[l5j.

6. Множество всех задаинй конечным числом породдаззцях е опрэдолящих соотношений групп с разретшлой проблемой равенства максимально б класса 2-і з иерархии Юптнк - Постовского

[15J.

йэль работы - доказать для конечно поровдзішнх относительно свободных (как правило, к. а. т.) групп аналога некоторых праве дзгашх виза результатов, касаасихсл к. о. идя конечно порожденных групп.

Иетодр исследования. Основним катодом диссертация является метод Ю. Г. Клеймана А, 16j„ который в свои очередь восходят к идеям работ 17, 18 J.

Научная новизна. Результаты диссертаций является еозш.ш и состоят в следующем (подробнее - пря HESOSOHSH СОДврйаНЕЯ

is. W. W. Воопе, Н- Relets,Jfc. Ort а ргоИепг о J.H.C. Whitehead and а ргоШм- о г Atonzo Скигск II Mk. Scand, №,уЛЗ,№,р.№-132.

16. Ю. Г. Клейман. О некоторых вопросах теория кногообраэий груш // Изв. № СССР, сор. шт., 1983, т. 47, й 1, с. 37-74.

17. M.R. Vau^lian - Lee. Uncou^aUy many т-rieiles ox qioups II Bull. London AfaU. Soc,

18. В. А. Романьков. 0 неразрешимости проблема задонорФаоЗ сводоіоств в овободккх нкльпотеитпых группах 2 в свободных кольцах // Алгебра и логика, 1977, т. 16, В 4, о. 457-471.

работы^.

1. Указано несколько кераспоппаааег/их свойств в класса 2-пороядеіпшх разросткмых к. з. т. групп п одно нераспознаваемое свойство в классо разрешимых к. б. многообразий групп.

2. Доказано, что в жсбоЗ (рекурсивно поречислимой) С-стопепп а потривиальной наследственной Щ-степени содержатся проблеял равенства некоторой 2-псроядо:шой разреянмой относительно свободной (к. з. т.) группа.

3. Приведен прилор 2-порсвдонноЗ разрешимой к. з. т. группы, в которой разрепгака проблема равенства, но нераэрешиыа проблема тождественных соотношений.

4. Доказало отсутствие равномерного алгоритма, регаахзэго проблему равенства по произвольному заданию двумя пороэдахсшия п конечним числом тачдествотшх соотношения разрешимой группы, в котороЗ эта проблема разрешима.

5. Для многих естественных классов конечных заданий относительно свободных групп определено место в иерархии Клини -Г'остовского шояеетва всэх заданій из данного класса, опрэде-ляедах группы с разрешимой проблемой равенства.

Теологическая д практическая ценность. Работа носат теоретический характер. Ее результаты могут быть полезны специалистам по алгоритмической теории групп и многообразий групп.

Апробация работы. Результаты днесортацдл частично докладывалась на научно-исследовательской семинаре по алгебре маха-нзко-катематачоского факультета ИГУ.

Публикации. Результаты диссертации опубликованы в двух работах, указанных в конце автореферата.

Структур* я объем работн. Диссертация выполнена на 100 страницах тайнописного текста а состоит из введения, пятя па-

раграфов, списка литературы, содержащего 27 наименований, и указателя обозначений.