Kompleksitas Keanggotaan-Pengujian untuk kelompok abelian terbatas

Pertimbangkan masalah tes keanggotaan abelian-subkelompok berikut ini .

Input:

Sebuah kelompok abelian berhingga dengan sewenang-wenang-besar . $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ $d_i$

Sebuah pembangkit-set dari subkelompok . $\lbrace h_1,\ldots,h_n\rbrace$ $H\subset G$

Sebuah elemen . $b\in G$

Keluaran: 'ya' jika dan 'tidak' di tempat lain '. $b\in H$

Pertanyaan: Bisakah masalah ini diselesaikan secara efisien di komputer klasik? Saya menganggap algoritma yang efisien jika menggunakan sumber daya waktu dan memori dalam arti biasa dari mesin Turing klasik. Perhatikan bahwa kita dapat mengasumsikan untuk setiap subgrup . Ukuran input dari masalah ini adalah . $O(\text{polylog}|G|)$ $n= O(\log|G|)$ $H$ $\lceil \log|G|\rceil$

Sedikit motivasi . Secara intuitif sepertinya masalah dapat diatasi dengan algoritma untuk menyelesaikan sistem linear kongruensi atau persamaan linear diophantine (baca di bawah). Namun, tampaknya ada perbedaan konsep efisiensi komputasi yang digunakan dalam konteks perhitungan dengan bilangan bulat, seperti: waktu polinomial kuat versus lemah, kompleksitas aljabar versus bit. Saya bukan ahli definisi ini dan saya tidak dapat menemukan referensi yang jelas menjawab pertanyaan ini.

Perbarui: jawaban untuk masalahnya adalah "ya".

Dalam jawaban terakhir, saya mengusulkan metode berdasarkan pada formulir normal Smith yang efisien untuk kelompok mana pun dengan formulir yang ditentukan.

Sebuah jawaban oleh Blondin menunjukkan bahwa dalam kasus tertentu di mana semua adalah dalam bentuk dan adalah "bilangan bulat kecil" maka masalahnya adalah . Bilangan bulat kecil secara eksponensial kecil dengan ukuran input: . $d_i$ $d_i= N_i^{e_i}$ $N_i, e_i$ $\text{NC}^3\subset \text{P}$ $O(\log\log|A|)$

Dalam jawaban saya, saya menggunakan "subkelompok ortogonal" untuk menyelesaikan masalah ini, tetapi saya percaya ini tidak perlu. Saya akan mencoba memberikan jawaban yang lebih langsung di masa depan berdasarkan metode baris Eselon bentuk yang saya baca.

Beberapa pendekatan yang mungkin

Masalahnya berkaitan erat dengan penyelesaian sistem linear kongruensi dan / atau persamaan diofantin linier. Saya meringkas koneksi ini secara singkat untuk penyelesaian.

Ambil menjadi matriks yang kolomnya adalah elemen dari set himpunan . Sistem persamaan berikut $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}$

memiliki solusi jika dan hanya jika . $b\in H$

Jika semua faktor siklik memiliki dimensi yang sama ada algoritma berdasarkan pada bentuk normal Smith yang memecahkan masalah dalam waktu polinomial. Dalam hal ini, algoritma yang efisien dari [1] menemukan bentuk normal Smith dari : ia mengembalikan matriks diagonal dan dua matriks yang dapat dibalik dan sedemikian rupa sehingga . Ini mengurangi masalah untuk menyelesaikan sistem sistem yang setara dengan diagonal. Kita dapat memutuskan secara efisien jika sistem memiliki solusi menggunakan algoritma Euclidean. $d=d_i$ $A$ $D$ $U$ $V$ $D=UAV$ $DY=Ub \mod d$ $D$

Contoh di atas menunjukkan bahwa masalah dapat diselesaikan secara efisien menggunakan teknik serupa dalam kasus umum. Kita dapat mencoba memecahkan sistem melakukan operasi modular, atau dengan mengubah sistem menjadi sistem yang lebih besar dari persamaan linear diophantine. Beberapa teknik yang mungkin untuk mendekati masalah yang dapat saya pikirkan adalah:

Komputasi bentuk-bentuk yang normal Smith dari . $A$
Komputasi baris Eselon bentuk . $A$
Eliminasi eliminasi Gaussian.

ds.algorithms time-complexity matrices nt.number-theory gr.group-theory Juan Bermejo Vega
sumber

secara bersamaan crossposted di MO: mathoverflow.net/questions/81300/…

Suresh Venkat

Tampaknya Anda telah melakukan crosspost atas pertanyaan ini secara bersamaan . Meskipun kami tidak keberatan dengan pertanyaan yang diposting ulang , kebijakan situs kami adalah mengizinkan repost hanya setelah waktu yang cukup telah berlalu dan Anda tidak mendapatkan jawaban yang diinginkan di tempat lain, karena crossposting simultan upaya duplikat dan diskusi fraktur. Anda dapat menandai pertanyaan ini untuk ditutup sekarang, dan kemudian reflag untuk dibuka jika perlu setelah merangkum diskusi yang relevan dari situs lain.

Suresh Venkat

Ditutup atas permintaan poster asli (karena duplikasi pada MO).

Dave Clarke

Saya mengirim jawaban sebelum posting ditutup. Menurut pendapat saya, pertanyaan ini lebih cocok di sini daripada pada aliran matematika karena telah dipelajari secara luas dalam literatur teori kompleksitas.

Michael Blondin

dibuka kembali atas permintaan OP; fokus pada kerumitan membuatnya cocok untuk di sini.

Suresh Venkat

Jawaban:

Memverifikasi apakah (di mana adalah vektor menurut komentar OP) sama dengan memverifikasi apakah ada solusi untuk sistem ini: $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}$

Dalam kasus Anda adalah angka kecil (mis. Nilainya logartihmic dalam ukuran input). Sayangnya, sepertinya kita tidak dapat menganggap bahwa berukuran kecil. $e_1, \ldots, e_N$ $d_1, \ldots, d_n$

Jika ya, maka Anda dapat menemukan solusi untuk sistem di dari hasil McKenzie & Cook [1] . Makalah ini menunjukkan bahwa penyelesaian kongruensi linear modulo integer dengan faktor kecil (LCON) ada di . Selain itu, masalah ini adalah setara dengan masalah keanggotaan grup permutasi abelian (RUPS). Tesis doktoral McKenzie sepenuhnya dikhususkan untuk masalah-masalah itu [1] . Baru-baru ini, masalah-masalah itu dipertimbangkan oleh Arvind & Vijayaraghavan [3] . $\text{NC}^3$ $\text{NC}^3$ $\text{NC}^1$

[1] Pierre McKenzie & Stephen A. Cook. Kompleksitas paralel dari masalah kelompok permutasi Abelian. 1987.

[2] Pierre McKenzie. Kompleksitas paralel dan kelompok permutasi. 1984.

[3] V. Arvind & TC Vijayaraghavan. Klasifikasi Masalah pada Kongruensi Linier dan Grup Permutasi Abelian Menggunakan Kelas Penghitungan Logspace. 2010

Michael Blondin
sumber

Terima kasih, unfortunatley saya tidak memiliki akses ke makalah ini sampai Senin. Ini mengejutkan saya bahwa ini bekerja untuk semua kelompok abelian. Untuk , yang abelian, menentukan apakah milik melibatkan memutuskan apakah memiliki solusi. Saya melihat dua masalah di sini: 1) Klasik sulit untuk menghitung fungsi totient Euler 2) Ini adalah versi keputusan dari logaritma diskrit. Masalahnya berkurang untuk memecahkan persamaan modular jika dekomposisi siklik diberikan. Bagaimana Anda mengatasi masalah ini? Apakah saya melewatkan sesuatu yang penting di sini?

Z_{N}^{*}

$Z_N^*$

b

$b$

⟨ a ⟩

$\langle a \rangle$

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

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

Juan Bermejo Vega

Sebenarnya, ini untuk grup permutasi abelian .

Michael Blondin

Saya akan melihat makalah ini dan mencoba mengatur semuanya sedikit. Terima kasih.

Juan Bermejo Vega

Bisakah Anda memberikan detail lebih lanjut tentang pengkodean input? Dengan cara ini, saya mungkin dapat meningkatkan jawaban saya.

Michael Blondin

Dekomposisi grup sebagai input (ini akan berupa string dengan beberapa angka dan panjangnya kurasa). Lalu, setiap elemen grup adalah dalam bentuk dan dapat diwakili oleh sejumlah angka. Untuk menyimpannya Anda perlu bits. Apakah ini menjawabnya?

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

Setelah beberapa waktu, saya berhasil menemukan algoritma yang mungkin tidak optimal tetapi sederhana yang membuktikan bahwa kompleksitas masalahnya adalah polinomial.

Algoritma

(a) Hitunglah sebuah pembangkit-set subkelompok orthogonal dari . $H^{\perp}$ $H$

(B) Periksa apakah elemen adalah ortogonal ke . $b$ $H^{\perp}$

Ada algoritma klasik yang efisien untuk masalah (a) dan (b) (lihat analisis di bawah). Hal ini memberikan keanggotaan-test efisien karena unsur adalah orthogonal untuk jika dan hanya jika . $b$ $H^\perp$ $h\in H$

Analisis

Subkelompok ortogonal didefinisikan melalui grup karakter sebagai: Properti utama: $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}$ adalah subkelompok . $G$
$H^{\perp^\perp}=H$

Algoritma untuk (a) :

Saya mengikuti algoritma dari [ 1 ] dengan variasi kecil. milik jika dan hanya jika untuk semua , tetapi, secara linearitas sudah cukup untuk menunjukkan untuk setiap generator dari . Memperluas karakter dalam hal eksponensial (di sini saya secara implisit menggunakan dekomposisi faktor siklik) kondisi ini setara dengan Untuk menyelesaikan persamaan ini, hitung menggunakan algoritma Euclidean dan angka $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$ . Kita dapat menulis kembali kondisi di atas untuk setiap sebagai sistem persamaan modular linier.

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}$ Seperti yang dibuktikan dalam 1 , jika kita mencicipi solusi acak sistem ini persamaan kita akan memperoleh himpunan menghasilkan dengan probabilitas secara eksponensial dekat dengan satu .

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$ . Di sini adalah matriks persegi panjang di atas bilangan bulat modulo yang algoritma yang diberikan dalam 2 memungkinkan untuk secara efisien menghitung dekomposisi normal Smith-nya. Algoritme mengembalikan matriks diagonal dan dua matriks yang dapat dibalik , sedemikian rupa sehingga . Dengan menggunakan rumus ini, sistem persamaan dapat ditulis sebagai dengan . Sekarang adalah mungkin untuk solusi secara acak menghitung dari menggunakan algoritma Euclid, karena ini adalah sistem persamaan dalam bentuk . Akhirnya, komputasi

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$ seseorang memperoleh elemen acak dari kelompok ortogonal seperti yang diinginkan.

H^{⊥}

$H^{\perp}$

Algoritma untuk (b) :

Karena kita sudah tahu bagaimana menghitung pembangkit-set , mudah untuk memeriksa apakah suatu unsur tertentu milik . Pertama hitung dari . Maka, menurut definisi, milik jika dan hanya jika untuk semua generator . Karena ada nomor O (polylog ( )) dari mereka dan ini dapat dilakukan secara efisien menggunakan aritmatika modular, kita selesai. $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
sumber

tidak apa-apa untuk menambahkan jawaban Anda sendiri jika Anda telah membuat penemuan untuk sementara waktu. Namun, sepertinya Anda perlu melakukan penyelidikan lebih lanjut (berdasarkan komentar Anda) sebelum Anda memutuskan jawaban mana yang akan diterima.

Suresh Venkat

Terima kasih. Saya ingin membuat diskusi lebih jauh untuk melihat apakah kita meletakkan semuanya dalam satu gambar. Juga, saya pikir mungkin ada algoritma yang lebih praktis yang bisa muncul.

Juan Bermejo Vega