Złożoność testowania członkostwa dla skończonych grup abelowych

Rozważ następujący problem testowania członkostwa w podgrupie abelian .

Wejścia:

Skończona grupa abelowa $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ o dowolnie dużych $d_i$ .

Wytwarzające osadzone $\lbrace h_1,\ldots,h_n\rbrace$ podgrupy $H\subset G$ .

Element $b\in G$ .

Wyjście: „tak”, jeżeli $b\in H$ i „nie” w innym miejscu.

Pytanie: Czy ten problem można skutecznie rozwiązać na klasycznym komputerze? Uważam algorytm efektywny jeśli używa $O(\text{polylog}|G|)$ czasu i zasobów pamięci w zwykłym znaczeniu klasycznych maszyn Turinga. Należy zauważyć, że można założyć, $n= O(\log|G|)$ dla każdej podgrupy $H$ . Rozmiar wejściowy tego problemu wynosi $\lceil \log|G|\rceil$ .

Trochę motywacji . Intuicyjnie wygląda na to, że problem można rozwiązać za pomocą algorytmów do rozwiązywania liniowych układów zgodności lub liniowych równań diofantycznych (czytaj poniżej). Wydaje się jednak, że istnieją różne pojęcia wydajności obliczeniowej stosowane w kontekście obliczeń z liczbami całkowitymi, takie jak: silnie versus słabo wielomianowy czas, algebraiczna versus złożoność bitowa. Nie jestem ekspertem od tych definicji i nie mogę znaleźć odniesienia, które jednoznacznie rozstrzygałoby to pytanie.

Aktualizacja: odpowiedź na problem brzmi „tak”.

W późnej odpowiedzi zaproponowałem metodę opartą na normalnych formach Smitha, która jest skuteczna dla każdej grupy o przepisanej formie.

Odpowiedź pokazy blondin, że w szczególności w przypadku, gdy wszystkie są postaci i są liczbami całkowitymi, „małe”, to problem należy do . Małe liczby całkowite są wykładniczo małe o wielkości wejściowej: . $d_i$ $d_i= N_i^{e_i}$ $N_i, e_i$ $\text{NC}^3\subset \text{P}$ $O(\log\log|A|)$

W mojej odpowiedzi użyłem „podgrup ortogonalnych”, aby rozwiązać ten problem, ale uważam, że nie jest to konieczne. Postaram się udzielić bardziej bezpośredniej odpowiedzi w oparciu o metodę, którą czytam w formie formularzy Echelon.

Niektóre możliwe podejścia

Problem jest ściśle związany z rozwiązywaniem liniowego układu zgodności i / lub liniowych równań diofantycznych. Podsumowuję te połączenia w celu uzupełnienia.

Weźmy jako macierz, której kolumny są elementami zestawu generującego . Poniższy układ równań $A$ $\lbrace h_1, \ldots, h_n \rbrace$

A x^{T} = (\begin{matrix} h_{1} (1) & h_{2} (1) & \dots & h_{n} (1) \\ h_{1} (2) & h_{2} (2) & \dots & h_{n} (2) \\ ⋮ & ⋮ & \dots & ⋮ \\ h_{1} (m) & h_{2} (m) & \dots & h_{n} (m) \end{matrix}) (\begin{matrix} x (1) \\ x (2) \\ ⋮ \\ x (n) \end{matrix}) = (\begin{matrix} b (1) \\ b (2) \\ ⋮ \\ b (m) \end{matrix}) \begin{matrix} \mod d_{1} \\ \mod d_{2} \\ ⋮ \\ \mod d_{m} \end{matrix}

$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}$

ma rozwiązanie tylko wtedy, gdy . $b\in H$

Jeśli wszystkie czynniki cykliczne mają ten sam wymiar istnieje algorytm oparty na normalnych formach Smitha, który rozwiązuje problem w czasie wielomianowym. W tym przypadku skuteczny algorytm z [1] znajduje normalną postać Smitha : zwraca macierz diagonalną i dwie odwracalne macierze i tak że . Zmniejszyło to problem rozwiązania równoważnego systemu systemowego z przekątnąMożemy skutecznie decydować, czy system ma rozwiązanie wykorzystujące algorytm euklidesowy. $d=d_i$ $A$ $D$ $U$ $V$ $D=UAV$ $DY=Ub \mod d$ $D$

Powyższy przykład sugeruje, że problem można skutecznie rozwiązać za pomocą podobnych technik w ogólnym przypadku. Możemy spróbować rozwiązać układ wykonując operacje modułowe lub przekształcając go w większy układ liniowych równań diofantycznych. Niektóre możliwe techniki podejścia do problemu, o których mogę myśleć, to:

Obliczanie normalnych form według Smitha . $A$
Obliczanie macierz schodkowa z . $A$
Całkowita eliminacja Gaussa.

— Juan Bermejo Vega
źródło

jednocześnie crossposted na MO: mathoverflow.net/questions/81300/…

— Suresh Venkat

Wygląda na to, że przesłuchałeś to pytanie jednocześnie . Chociaż nie mamy nic przeciwko ponownej publikacji pytania , nasze zasady dotyczące witryn zezwalają na repost dopiero po upływie wystarczającego czasu, a ty nie uzyskałeś pożądanej odpowiedzi w innym miejscu, ponieważ jednoczesne kopiowanie krzyżowe powiela wysiłek i łamie dyskusję. Możesz oflagować to pytanie, aby je zamknąć, a następnie, jeśli to konieczne, po streszczeniu odpowiednich dyskusji z innych stron, przeflaguj je w celu otwarcia.

— Suresh Venkat

Zamknięte na żądanie oryginalnego plakatu (z powodu powielania w MO).

— Dave Clarke,

Odpowiedziałem przed zamknięciem posta. Moim zdaniem pytanie to jest bardziej odpowiednie w tym przypadku niż w matematycznym przepływie, ponieważ zostało szeroko zbadane w literaturze teorii złożoności.

— Michael Blondin,

ponownie otwarte na wniosek PO; skupienie się na złożoności sprawia, że jest to odpowiednie rozwiązanie.

— Suresh Venkat

Odpowiedzi:

Weryfikacja, czy (gdzie są wektorami zgodnie z komentarzami PO) jest równoważne ze sprawdzeniem, czy istnieje rozwiązanie dla tego systemu: $b \in \langle h_1, \ldots, h_n\rangle$ $h_i$

(\begin{matrix} h_{1} (1) & \dots & h_{n} (1) & d_{1}^{e_{1}} & 0 & \dots & 0 \\ ⋮ & ⋱ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ h_{1} (m) & \dots & h_{n} (m) & 0 & 0 & \dots & d_{m}^{e_{N}} \end{matrix}) (\begin{matrix} x (1) \\ ⋮ \\ x (n) \\ y (1) \\ ⋮ \\ y (m) \end{matrix}) \equiv (\begin{matrix} b (1) \\ ⋮ \\ b (m) \end{matrix})

$\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}$

W twoim przypadku są małymi liczbami (tzn. Ich wartość jest logartihmic w wielkości wejściowej). Niestety nie wydaje się, że możemy założyć, że są małe. $e_1, \ldots, e_N$ $d_1, \ldots, d_n$

Jeśli tak, to możesz znaleźć rozwiązanie dla systemu w z wyniku McKenzie & Cook [1] . Ten artykuł pokazuje, że rozwiązywanie liniowych przystawek modulo liczba całkowita z małymi czynnikami (LCON) jest w . Co więcej, ten problem jest równoważny z problemem członkostwa w grupie permutacji abelowej (AGM). Praca doktorska McKenziego jest w pełni poświęcona tym problemom [1] . Niedawno problemy te zostały rozważone przez Arvind i Vijayaraghavan [3] . $\text{NC}^3$ $\text{NC}^3$ $\text{NC}^1$

[1] Pierre McKenzie i Stephen A. Cook. Równoległa złożoność problemów grup permutacyjnych Abeliana. 1987.

[2] Pierre McKenzie. Równoległe grupy złożoności i permutacji. 1984.

[3] V. Arvind i TC Vijayaraghavan. Klasyfikowanie problemów w liniach zbiegów i grupach permutacji abelowej za pomocą klas zliczania przestrzeni logicznej. 2010 r.

— Michael Blondin
źródło

Dzięki, niestety nie mam dostępu do tych dokumentów do poniedziałku. Zaskakuje mnie, że działa to dla każdej grupy abelowej. Dla , który jest , ustalenie, czy należy do wymaga podjęcia decyzji, czy ma rozwiązanie. Widzę tutaj dwa problemy: 1) Klasycznie trudno jest obliczyć funkcję totulową Eulera 2) Jest to wersja decyzyjna logarytmu dyskretnego. Problem sprowadza się do rozwiązywania równań modułowych, jeśli podano cykliczny rozkład. Jak poradzisz sobie z tym problemem? Czy brakuje mi czegoś ważnego tutaj?

Z_{N}^{*}

$Z_N^*$

b

$b$

⟨ a ⟩

$\langle a \rangle$

b = a^{i} \mod φ (N)

$b=a^i\mod \varphi(N)$

— Juan Bermejo Vega

Właściwie to dla każdej grupy permutacji abelowej .

— Michael Blondin,

Rzućę okiem na te dokumenty i staram się wszystko trochę uporządkować. Dzięki.

— Juan Bermejo Vega

Czy możesz podać więcej szczegółów na temat kodowania wejścia? W ten sposób mogę poprawić swoją odpowiedź.

— Michael Blondin,

Rozkład grupy jako dane wejściowe (byłyby to ciąg z kilkoma liczbami i długość chyba). Następnie każdy element grupy ma postać i może być reprezentowany przez krotkę liczb. Aby go zapisać, potrzebujesz bitów. Czy to odpowiada?

A = Z_{d_{1}} \times Z_{d_{1}} \dots \times Z_{d_{N}}

$A=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_N}$

(g_{1}, \dots, g_{n})

$(g_1,\ldots,g_n)$

n := ⌈ l o g_{2} | A | ⌉

$n:= \lceil log_2 |A|\rceil$

— Juan Bermejo Vega

Po pewnym czasie udało mi się znaleźć być może nieoptymalny, ale prosty algorytm, który dowodzi, że złożoność problemu jest wielomianowa.

Algorytm

(a) Obliczenie wytwarzające osadzone ortogonalnego podgrupy o . $H^{\perp}$ $H$

(b) Sprawdź, czy element jest ortogonalny względem . $b$ $H^{\perp}$

Istnieją wydajne algorytmy klasyczne dla problemów (a) i (b) (patrz analiza poniżej). Daje to efektywne członkostwa testu, ponieważ element jest prostopadła do wtedy i tylko wtedy . $b$ $H^\perp$ $h\in H$

Analiza

Ortogonalna podgrupa jest zdefiniowana poprzez grupę znaków jako: Główne właściwości: $H^{\perp}$ $G$

H^{⊥} := {g \in G : χ_{g} (h) = 1 \forall h \in H}

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

$H^{\perp}$ jest podgrupą . $G$
$H^{\perp^\perp}=H$

Algorytm dla (a) :

Postępuję zgodnie z algorytmem z [ 1 ] z niewielkimi zmianami. należy do wtedy i tylko wtedy, gdy dla wszystkich , ale liniowo wystarczy pokazać dla każdy generator . Rozszerzanie znaku pod względem wykładniczym (tutaj domyślnie używam cyklicznego rozkładu czynników) warunek ten jest równoważny z Aby rozwiązać te równania, oblicz przy użyciu algorytmu euklidesowego i liczb $g$ $H^{\perp}$ $\chi_{g}(h)=1$ $h\in H$ $\chi_{b}(h_i)=1$ $H$

\begin{array}{rcl} \exp {2 π i (\frac{g (1) h_{i} (1)}{d_{1}} + \dots + \frac{g (m) h_{i} (m)}{d_{m}})} = 1 \end{array}

$\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 := lcm (N_{1}, \dots, N_{d})

$M:= \text{lcm}(N_1,\ldots,N_d)$

α_{i} := M / d_{i}

$\alpha_i:=M/d_i$ . Możemy ponownie napisać powyższe warunki dla każdego jako systemu liniowych równań modułowych.

i

$i$

(\begin{matrix} α_{1} h_{1} (1) & α_{2} h_{1} (2) & \dots & α_{m} h_{1} (m) \\ α_{1} h_{2} (1) & α_{2} h_{2} (2) & \dots & α_{m} h_{2} (m) \\ ⋮ & ⋮ & \dots & ⋮ \\ α_{1} h_{n} (1) & α_{2} h_{n} (2) & \dots & α_{m} h_{n} (m) \end{matrix}) (\begin{matrix} g (1) \\ g (2) \\ ⋮ \\ g (n) \end{matrix}) = (\begin{matrix} 0 \\ 0 \\ ⋮ \\ 0 \end{matrix}) \begin{matrix} \mod M \\ \mod M \\ ⋮ \\ \mod M \end{matrix}

$\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}$ Jak zostało udowodnione w 1 , jeśli spróbujemy losowych rozwiązań tego systemu równań otrzymamy zestaw generujący z prawdopodobieństwem wykładniczo zbliżonym do jednego .

t + ⌈ \log | G | ⌉

$t+\lceil\log|G|\rceil$

H^{⊥}

$H^{\perp}$

p \geq 1 - 1 / 2^{t}

$p\geq 1 -1/2^{t}$

A X = 0 (\mod M)

$AX=0 \pmod M$ . Tutaj jest prostokątną macierzą nad liczbą całkowitą modulo dla której algorytm podany w 2 pozwala skutecznie obliczyć normalny rozkład Smitha. Algorytm zwraca macierz diagonalną i dwie macierze odwracalne , takie, że . Za pomocą tej formuły układ równań można zapisać jako z . Teraz możliwe jest losowo obliczeniowych rozwiązań z wykorzystaniem algorytmu Euklidesa, ponieważ jest to układ równań w postaci . Na koniec obliczenie

A

$A$

M

$M$

D

$D$

U

$U$

V

$V$

D = U A V

$D=UAV$

D Y = 0 (\mod M)

$DY=0 \pmod M$

X = V Y

$X=VY$

D Y = 0 (\mod M)

$DY=0\pmod M$

d_{i} y_{i} = 0 (\mod M)

$d_i y_i =0 \pmod M$

X = V Y

$X=VY$ uzyskuje się losowy element grupy ortogonalnej według potrzeb.

H^{⊥}

$H^{\perp}$

Algorytm dla (b) :

Skoro już wiemy, w jaki sposób obliczyć wytwarzającego-zestaw , to jest łatwe do sprawdzenia, czy dany element należący do . Najpierw oblicz zestaw generatora z . Następnie z definicji należy do wtedy i tylko wtedy, gdy dla wszystkich generatorów . Ponieważ jest ich liczba O (polilog ( )) i można to zrobić skutecznie za pomocą arytmetyki modułowej, jesteśmy gotowi . $H^{\perp}$ $b$ $H$ $\langle g_1,\ldots, g_s \rangle$ $H^{\perp}$ $b$ $H$ $\chi_{b}(g_i)=1$ $H^{\perp}$ $|G|$

— Juan Bermejo Vega
źródło

możesz dodać własną odpowiedź, jeśli w międzyczasie dokonałeś odkrycia. Wygląda jednak na to, że musisz jeszcze trochę zbadać (na podstawie swojego komentarza), zanim zdecydujesz, którą odpowiedź zaakceptować.

— Suresh Venkat,

Dzięki. Chciałbym kontynuować dyskusję, aby zobaczyć, czy umieścimy wszystko w jednym obrazie. Myślę też, że może istnieć bardziej praktyczny algorytm, który mógłby się wyskoczyć.

— Juan Bermejo Vega