Сложность членства-тестирования для конечных абелевых групп

12

Рассмотрим следующую задачу проверки принадлежности к абелевой подгруппе .

Входы:

  1. Конечная абелева группа с произвольно большим .G=Zd1×Zd1×Zdmdi

  2. Производящая-набор {h1,,hn} подгруппы HG .

  3. Элемент bG .

Вывод: «да», если bH и «нет» в другом месте.

Вопрос: Можно ли эффективно решить эту проблему на классическом компьютере? Я считаю алгоритм эффективным, если он использует O(polylog|G|) ресурсы времени и памяти в обычном смысле классических машин Тьюринга. Обратите внимание , что мы можем считать n=O(log|G|) для любой подгруппы H . Входной размер этой проблемы log|G| .

Немного мотивации . Интуитивно кажется, что проблема может быть решена с помощью алгоритмов для решения линейных систем сравнений или линейных диофантовых уравнений (см. Ниже). Тем не менее, кажется, что существуют различные понятия эффективности вычислений, используемые в контексте вычислений с целыми числами, такие как: строго по сравнению со слабо полиномиальным временем, по алгебраической или по битовой сложности. Я не эксперт по этим определениям, и я не могу найти ссылку, которая четко решает этот вопрос.

Обновление: ответом на проблему является «да».

  • В последнем ответе я предложил метод, основанный на нормальных формах Смита, который эффективен для любой группы с установленной формой.

  • Ответ Блондина показывает, что в конкретном случае, когда все имеют вид и - «крошечные целые числа», тогда проблема принадлежит . Крошечные целые числа экспоненциально малы с входным размером: .d i = N e i i N i , e i NC 3P O ( log log | A | )didi=NieiNi,eiNC3PO(loglog|A|)

В своем ответе я использовал «ортогональные подгруппы» для решения этой проблемы, но я считаю, что в этом нет необходимости. Я постараюсь дать более прямой ответ в будущем, основываясь на методе строчных форм Echelon, который я читаю.


Некоторые возможные подходы

Задача тесно связана с решением линейной системы сравнений и / или линейных диофантовых уравнений. Я кратко суммирую эти связи ради завершения.

Возьмем в качестве матрицы, столбцы которой являются элементами порождающего множества . Следующая система уравнений{ h 1 , A{h1,,hn}

AxT=(h1(1)h2(1)hn(1)h1(2)h2(2)hn(2)h1(m)h2(m)hn(m))(x(1)x(2)x(n))=(b(1)b(2)b(m))modd1modd2moddm

имеет решение тогда и только тогда , когда .bH

Если все циклические факторы имеют одинаковую размерность существует алгоритм, основанный на нормальных формах Смита, который решает проблему за полиномиальное время. В этом случае эффективный алгоритм из [1] находит нормальную форму Смита : он возвращает диагональную матрицу и две обратимые матрицы и такие что . Это сводило задачу к решению системы эквивалентных систем с диагональюМы можем эффективно решить, если система имеет решение, используя евклидов алгоритм. A D U V D = U A V Dd=diADUVD=UAVDDY=UbmoddD

Приведенный выше пример предполагает, что проблема может быть эффективно решена с использованием аналогичных методов в общем случае. Мы можем попытаться решить систему, выполнив модульные операции или превратив систему в большую систему линейных диофантовых уравнений. Вот некоторые возможные методы решения этой проблемы:

  1. Вычисление Смита нормальных форм .A
  2. Вычисление строки Echelon формы .A
  3. Целочисленное гауссово исключение.
Хуан Бермехо Вега
источник
1
одновременно размещен на МО: mathoverflow.net/questions/81300/…
Суреш Венкат
2
Похоже, что вы поставили этот вопрос одновременно . Хотя мы не возражаем против повторного размещения вопроса , наша политика сайта заключается в том, чтобы разрешать повторное размещение только после того, как прошло достаточное количество времени, и вы не получили желаемого ответа в другом месте, поскольку одновременное перекрестное размещение дублирует обсуждение усилий и переломов. Вы можете пометить этот вопрос как закрывающий сейчас, а затем, при необходимости, пометить его как открывающий после подведения итогов соответствующих обсуждений с других сайтов.
Суреш Венкат
1
Закрыт по запросу оригинального постера (из-за дублирования на МО).
Дейв Кларк
1
Я отправил ответ до того, как сообщение было закрыто. На мой взгляд, этот вопрос лучше подходит здесь, чем на mathoverflow, поскольку он широко изучался в литературе по теории сложности.
Михаил Блондин
1
возобновлено по запросу OP; сосредоточиться на сложности делает его подходящим для здесь.
Суреш Венкат

Ответы:

10

Проверка того, является ли (где - векторами согласно комментариям ОП) эквивалентна проверке, существует ли решение для этой системы: ч я ( ч 1 ( 1 ) ч н ( 1 ) д е 1 1 0 bh1,,hnhi

(h1(1)hn(1)d1e100h1(m)hn(m)00dmeN)(x(1)x(n)y(1)y(m))(b(1)b(m))

В вашем случае - это крошечные числа (т.е. их значение логарифмически во входном размере). К сожалению, не похоже, что мы можем предположить, что крошечные.d 1 , , d ne1,,eNd1,,dn

Если это так, то вы можете найти решение для системы в из результатов McKenzie & Cook [1] . Эта статья показывает, что решение линейных конгруэнций по модулю целого числа с крошечными множителями (LCON) находится в . Кроме того, эта задача -эквивалентна проблеме принадлежности к абелевой группе перестановок (AGM). Докторская диссертация Маккензи полностью посвящена этим проблемам [1] . Совсем недавно эти проблемы были рассмотрены Арвиндом и Виджаярагхаваном [3] .NC 3 NC 1NC3NC3NC1

[1] Пьер МакКензи и Стивен А. Кук. Параллельная сложность задач абелевой группы подстановок. 1987.

[2] Пьер МакКензи. Параллельные группы сложности и перестановки. 1984.

[3] В. Арвинд и Т. С. Виджаярагхаван. Классификация задач на линейных конгруэнциях и абелевых группах перестановок с использованием классов подсчета пространства журналов. 2010.

Майкл Блондин
источник
Спасибо, к сожалению, у меня нет доступа к этим документам до понедельника. Меня удивляет, что это работает для любой абелевой группы. Для , который является абелевым, определение, принадлежит ли к включает решение, имеет ли решение решение. Здесь я вижу две проблемы: 1) Классически сложно вычислить функцию Эйлера 2) Это вариант решения дискретного логарифма. Задача сводится к решению модульных уравнений, если задано циклическое разложение. Как вы обходите эту проблему? Я что-то упустил здесь? б б =ZNbab=aimodφ(N)
Хуан Бермехо Вега
На самом деле, это для любой группы абелевых перестановок .
Михаил Блондин
Я посмотрю на эти статьи и постараюсь все немного упорядочить. Благодарю.
Хуан Бермехо Вега
Не могли бы вы предоставить более подробную информацию о кодировке ввода? Таким образом, я мог бы улучшить свой ответ.
Михаил Блондин
A=Zd1×Zd1×ZdN(g1,,gn)n:=log2|A|
4

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

Алгоритм

HH

bH

bHhH


Анализ

HG

H:={gG:χg(h)=1hH}
  1. HG
  2. H=H

Алгоритм для (а) :

gHχg(h)=1hHχb(hi)=1H

exp{2πi(g(1)hi(1)d1++g(m)hi(m)dm)}=1
M:=lcm(N1,,Nd)αi:=M/dii

(α1h1(1)α2h1(2)αmh1(m)α1h2(1)α2h2(2)αmh2(m)α1hn(1)α2hn(2)αmhn(m))(g(1)g(2)g(n))=(000)modMmodMmodM
t+log|G|Hp11/2tAX=0(modM)AMDUVD=UAVDY=0(modM)X=VYDY=0(modM)diyi=0(modM)X=VYH

Алгоритм для (б) :

HbHg1,,gsHbHχb(gi)=1H|G|)) их количество, и это можно сделать эффективно, используя модульную арифметику, которую мы сделали.

Хуан Бермехо Вега
источник
1
Можно добавить свой ответ, если вы сделали открытия за это время. Тем не менее, кажется, что вам нужно провести дополнительное расследование (на основе вашего комментария), прежде чем вы решите, какой ответ принять.
Суреш Венкат
Благодарю. Я хотел бы продолжить обсуждение, чтобы увидеть, соединим ли мы все в одну картину. Кроме того, я думаю, что мог бы быть более практичный алгоритм, который мог бы появиться.
Хуан Бермехо Вега