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

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

Входы:

1. Конечная абелева группа с произвольно большим .$G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$$d_i$

2. Производящая-набор $\lbrace h_1,\ldots,h_n\rbrace$ подгруппы $H\subset G$ .

3. Элемент $b\in G$ .

Вывод: «да», если $b\in H$ и «нет» в другом месте.

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

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

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

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

• Ответ Блондина показывает, что в конкретном случае, когда все имеют вид и - «крошечные целые числа», тогда проблема принадлежит . Крошечные целые числа экспоненциально малы с входным размером: .d i = N e i i N i , e i NC 3 ⊂ P O ( log log | A |$d_i$$d_i= N_i^{e_i}$$N_i, e_i$$\text{NC}^3\subset \text{P}$$O(\log\log|A|)$

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

---

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

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

Возьмем в качестве матрицы, столбцы которой являются элементами порождающего множества . Следующая система уравнений{ h 1 , $A$$\lbrace h_1, \ldots, h_n \rbrace$

$$Ax^{T}= \begin{pmatrix} h_1(1) & h_2(1) & \ldots & h_n(1)\\ h_1(2) & h_2(2) & \ldots & h_n(2)\\ \vdots & \vdots & \cdots & \vdots\\ h_1(m) & h_2(m) & \ldots & h_n(m) \end{pmatrix} \begin{pmatrix} x(1)\\ x(2)\\ \vdots\\ x(n) \end{pmatrix} = \begin{pmatrix} b(1) \\ b(2) \\ \vdots\\ b(m) \end{pmatrix} \begin{matrix} \mod d_1\\ \mod d_2\\ \vdots\\ \mod d_m \end{matrix}$$

имеет решение тогда и только тогда , когда .$b\in H$

Если все циклические факторы имеют одинаковую размерность существует алгоритм, основанный на нормальных формах Смита, который решает проблему за полиномиальное время. В этом случае эффективный алгоритм из [1] находит нормальную форму Смита : он возвращает диагональную матрицу и две обратимые матрицы и такие что . Это сводило задачу к решению системы эквивалентных систем с диагональюМы можем эффективно решить, если система имеет решение, используя евклидов алгоритм. A D U V D = U A V $d=d_i$$A$$D$$U$$V$$D=UAV$$DY=Ub \mod d$$D$

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

1. Вычисление Смита нормальных форм .$A$
2. Вычисление строки Echelon формы .$A$
3. Целочисленное гауссово исключение.

Проверка того, является ли (где - векторами согласно комментариям ОП) эквивалентна проверке, существует ли решение для этой системы: ч я ( ч 1 ( 1 ) ⋯ ч н ( 1 ) д е 1 1 0 $b \in \langle h_1, \ldots, h_n\rangle$$h_i$

$$\begin{pmatrix} h_{1}(1) & \cdots & h_{n}(1) & d_1^{e_1} & 0 & \cdots & 0 \\\\ \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \vdots \\\\ h_{1}(m) & \cdots & h_{n}(m) & 0 & 0 & \cdots & d_m^{e_N} \end{pmatrix} \begin{pmatrix} x(1) \\\\ \vdots \\\\ x(n) \\\\ y(1) \\\\ \vdots \\\\ y(m) \end{pmatrix} \equiv \begin{pmatrix} b(1) \\\\ \vdots \\\\ b(m) \end{pmatrix}$$

В вашем случае - это крошечные числа (т.е. их значение логарифмически во входном размере). К сожалению, не похоже, что мы можем предположить, что крошечные.d 1 , … , d $e_1, \ldots, e_N$$d_1, \ldots, d_n$

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

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

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

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

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

Алгоритм

$H^{\perp}$$H$

$b$$H^{\perp}$

$b$$H^\perp$$h\in H$

---

Анализ

$H^{\perp}$$G$

$$H^{\perp}:= \{g\in G : \chi_g(h)=1\quad \forall h\in H \}$$

1. $H^{\perp}$$G$
2. $H^{\perp^\perp}=H$

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

$g$$H^{\perp}$$\chi_{g}(h)=1$$h\in H$$\chi_{b}(h_i)=1$$H$

$$\begin{eqnarray} \exp \left\lbrace 2\pi i \left( \frac{g(1)h_{i}(1)}{d_1}+\ldots + \frac{g(m) h_{i}(m)}{d_m} \right) \right\rbrace=1 \end{eqnarray}$$ $M:= \text{lcm}(N_1,\ldots,N_d)$$\alpha_i:=M/d_i$$i$

$$\begin{pmatrix} \alpha_1 h_1(1) & \alpha_2 h_1(2) & \ldots & \alpha_m h_1(m)\\ \alpha_1 h_2(1) & \alpha_2 h_2(2) & \ldots & \alpha_m h_2(m)\\ \vdots & \vdots & \cdots & \vdots\\ \alpha_1 h_n(1) & \alpha_2 h_n(2) & \ldots & \alpha_m h_n(m) \end{pmatrix} \begin{pmatrix} g(1)\\ g(2)\\ \vdots\\ g(n) \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots\\ 0 \end{pmatrix} \begin{matrix} \mod M\\ \mod M\\ \vdots\\ \mod M \end{matrix}$$ $t+\lceil\log|G|\rceil$$H^{\perp}$$p\geq 1 -1/2^{t}$$AX=0 \pmod M$$A$$M$$D$$U$$V$$D=UAV$$DY=0 \pmod M$$X=VY$$DY=0\pmod M$$d_i y_i =0 \pmod M$$X=VY$$H^{\perp}$

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

$H^{\perp}$$b$$H$$\langle g_1,\ldots, g_s \rangle$$H^{\perp}$$b$$H$$\chi_{b}(g_i)=1$$H^{\perp}$$|G|$)) их количество, и это можно сделать эффективно, используя модульную арифметику, которую мы сделали.