Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №4, Москва, 1992
Авторы: Кочергин В.В.
О сложности вычислений в конечных абелевых группах
Аннотация:
Множество элементов BG = {g1, . . . , gq} конечной абелевой (по умножению) группы G называется базисом, если группа G представляется в виде прямого произведения циклических групп, порожденных элементами g1, . . . , gq: G = бg1с× . . . × бgqс. Изучается вычисление элементов группы G схемами из функциональных элементов умножения, в которых каждый функциональный элемент вычисляет произведение подаваемой на его входы пары элементов группы G. Под сложностью L(S) схемы S понимается общее число функциональных элементов в схеме S. Сложность конечной абелевой группы G над базисом BG определяется равенством L(G, BG) = maxg∈G minS L(S), где минимум берется по всем схемам S, вычисляющим элемент g над базисом BG. В работе доказано, что при |G| → ∞ справедливо равенство
L(G,BG) = (log2|G| / log2log2|G|) (1+O(√ (log2log2log2|G| / log2log2|G|))) +O(p+|BG|) где p ̶̶ наибольший порядок у элементов из множества BG. Для функции Шеннона, определяемой равенством
L(n) = maxG:|G|=nminBGL(G,BG), при n → ∞ установлена асимптотическая формула L(n) = log2n + (1 + o(1))(log2n / log2log2n) Эти результаты основаны на использовании описанного в работе асимптотически оптимального метода реализации двоичных матриц ступенчатого вида вентильными схемами.
Ключевые слова:
конечная абелева группа, вентильная схема, схемная сложность, сложность группы, функция Шеннона
Язык публикации: русский, страниц: 40 (с. 178-217)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Кочергин Вадим Васильевич,  ,  Механико-математический факультет МГУ, Кафедра дискретной математики, Институт теоретических проблем микромира им. Н. Н. Боголюбова МГУ