Том 3, номер 1, 1996 г., Стр. 43-51

УДК 519.71
В. В. Кочергин
О сложности вычислений в конечных нильпотентных группах

Аннотация:
Исследуется задача о сложности вычислений элементов конечных нильпотентных групп, исходя из порождающих подмножеств при условии, что возможно многократное использование промежуточных результатов. Показывается, что для нильпотентных групп порядка $n$ вычисление осуществимо при использовании $O(\log n)$ групповых операций, и предъявлена группа порядка $n$, для которой сложность такого вычисления равна $(1+0(1))\log_2n$.
Библиогр. 6.

Кочергин В. В. ¹
1. МГУ, мех.-мат. факультет
Воробьевы горы, 119899 Москва, Россия

Статья поступила 15 января 1996 г.