Статья в сборнике "Математические вопросы кибернетики" №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)
Эти результаты основаны на использовании описанного в работе асимптотически оптимального метода реализации двоичных матриц ступенчатого вида вентильными схемами.
Ключевые слова:
конечная абелева группа, вентильная схема, схемная сложность, сложность группы, функция Шеннона
Кочергин Вадим Васильевич, , Механико-математический факультет МГУ, Кафедра дискретной математики, Институт теоретических проблем микромира им. Н. Н. Боголюбова МГУ