|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Об одной нижней оценке сложности вычисления элементов конечных абелевых группстатья
- Автор: Кочергин В.В.
- Сборник: Проблемы теоретической кибернетики. Материалы XVII Международной конференции (Казань, 16-20 июня 2014 г.)
- Серия: Проблемы теоретической кибернетики
- Год издания: 2014
- Место издания: Отечество Казань
- Первая страница: 155
- Последняя страница: 158
- Аннотация: Исследуется задача о сложности вычислений элементов конечных абелевых групп. Под сложностью вычисления элемента конечной абелевой группы над заданным базисом (здесь базис - такое подмножество группы, что группа является прямым произведением циклических групп с образующими из этого множества) понимается минимальное число операций для получения исходя из элементов базиса этого элемента (разрешается многократное использование результатов промежуточных вычислений). Сложность конечной абелевой группы над заданным базисом - это максимальная сложность элементов группы над этим базисом. Под сложностью конечной абелевой группы понимается максимум сложностей группы над различными базисами. Установлено, что сложность конечной абелевой группы растет (с ростом, например, порядка группы) асимптотически не медленнее чем сумма числа примарных компонент группы и логарифма максимального порядка среди элементов группы.
- Добавил в систему: Кочергин Вадим Васильевич