Apakah isomorfisme kelompok abel di ?

8

Sebuah berjalan algoritma waktu untuk isomorfisma grup abelian mudah untuk melihat. Kemudian mengerjakan masalah ini pada tahun 2003, Vikas meningkatkan hasil dari waktu berjalan ke . Pada tahun 2007, Kavitha menunjukkan bahwa isomorfisma kelompok abelian dapat dilakukan dalam waktu linier yaitu waktu .O(n2)O ( n log n )O(n2)O(nlogn)O(n)

Saya tahu bahwa isomorfisma kelompok abelian ketika kelompok diberikan oleh representasi tabel ada di . Apakah ada makalah penelitian atau artikel yang menunjukkan bahwa itu ada di ? Saya mencoba google tetapi hanya mendapatkan hasilnya di . A C 0 T C 0TC0AC0TC0

Pertanyaan: Apakah abelian group isomorphism (kelompok yang diberikan dalam representasi tabel) dalamAC0

baru
sumber
3
pertanyaan dalam cs, cs.stackexchange.com/questions/87369/is-finite-abelian-group-isomorphism-in-log-space - hasilnya menunjukkan subkelompok abelian dalam dan ; T C 0 ( F O L L )LTC0(FOLL)
user3483902
4
Anda sudah mengajukan pertanyaan serupa di CS.SE ( cs.stackexchange.com/q/87369/755 ) dan Anda sudah mendapat jawaban di sana yang memberikan kutipan ke makalah yang mempertimbangkan masalah ini. Mengapa Anda tidak menyebutkan bahwa Anda sudah mendapat jawaban dan mengutip makalah itu? Sudahkah Anda mencoba melakukan pencarian literatur mulai dari makalah itu, untuk mencari makalah lain yang mengutipnya atau yang mengutip untuk melihat apakah ada sesuatu dalam literatur tentang subjek? Anda harus melakukan pencarian literatur sendiri sebelum bertanya .... dan Anda harus merangkum jawaban lain yang sudah Anda dapatkan.
DW
3
Lebih baik (a) mengutip makalah, dan (b) melakukan pencarian literatur yang saya sarankan, dan (c) melaporkan hasil pencarian literatur dalam pertanyaan. Anda tidak menyebutkan apakah Anda melakukan pencarian literatur. Jika Anda telah melakukan pencarian literatur dan belum menemukan apa pun, mungkin itu tidak diketahui.
DW
3
Sebenarnya, referensi untuk klaim TC ^ 0 akan menyenangkan.
Emil Jeřábek
3
Tidak diketahui berada di TC0. Dengan demikian tidak diketahui berada di AC0.
Jane

Jawaban:

4

Bertentangan dengan apa yang dinyatakan dalam pertanyaan, isomorfisme kelompok abelian tidak diketahui berada di . Tidak perlu dikatakan, ini juga berarti tidak diketahui berada di . A C 0TC0AC0

Apa yang diketahui adalah pengamatan berikut dari [1]. Biarkan menunjukkan masalah berikut: diberi tabel perkalian grup abelian , elemen , dan di unary, tentukan apakah . Teorema struktur untuk grup abelian terbatas dengan mudah menyiratkan bahwa jika adalah dua kelompok ukuran , maka ( A , ) a , b A m b = a m A , B npow(A,)a,bAmb=amA,Bn

()ABmn|{aA:am=1}|=|{bB:bm=1}|.

Karena kita dapat menghitung set ukuran polinomial dalam , kita memperolehTC0

Proposisi 1: Abelian group isomorphism dapat dihitung dalam .TC0(pow)

Sekarang, jelas dapat dihitung dalam L, dan seperti yang ditunjukkan pada [2], juga di kelas FOLL. Jadi,pow

Konsekuensi 2: Isomorfisme kelompok Abel dapat dihitung dalam dan di .LTC0(FOLL)

Tidak diketahui apakah dapat dihitung dalam .powTC0

Tampaknya Corollary 2 adalah hasil yang paling dikenal ketika datang ke kelas sirkuit "polinomial-size" yang biasa. Namun, saya mengamati bahwa masalahnya ada di versi quasipolynomial dari :AC0

Proposisi 3: Isomorfisma kelompok Abelian dapat dihitung dengan urutan yang seragam dari sirkuit Boolean dengan kedalaman konstan ukuran-kuasipolinomial; lebih khusus, ini ada di .Σ2-TIME((logn)2)

(Ini diterjemahkan ke dalam keluarga seragam dari kedalaman-3 sirkuit ukuran , di mana disjunctions bawah memiliki fan-in hanya ; ini sering disebut "kedalaman ".) O ( ( log n ) 2 ) 2 12O((logn)2)O((logn)2)212

Proposisi 3 sekali lagi merupakan konsekuensi dari teorema struktur untuk grup abelian terbatas: setiap grup tersebut dapat ditulis sebagai jumlah langsung dari subkelompok siklik , sehingga grup dan adalah isomorfik jika mereka dapat ditulis sebagai jumlah langsung subkelompok siklik dengan pesanan yang cocok: yaitu, jika , maka iffA B | A | = | B | = n A BO(logn)AB|A|=|B|=nAB

terdapat

  • urutan dari integerk log n{mi:i<k}klognmin

  • urutan dan{ai:i<k}A{bi:i<k}B

seperti yang

  • i<kmi=n

  • aimi=1 dan untuk setiapbimi=1i<k

  • untuk semua urutan dari bilangan bulat , tidak semuanya nol:{ri:i<k}0ri<mi

    i<kairi1 dani<kbiri1

Dua bilangan utama disorot. Untuk melihat bahwa batas yang disebutkan tidak terlampaui, kita perlu menunjukkan bahwa identitas dapat diperiksa di . Ini dapat dilakukan dengan menebak secara berturut-turut dan memverifikasi nilai dari produk parsial untuk ; selain itu, untuk setiap , kami juga menebak dan memverifikasi hasil sebagian dari perhitungan dengan kuadrat berulang. Secara total, ini membuat menebak, masing-masing mengambili<kairi=1NTIME((logn)2)i<lairil=0,,kiO(logri)airiO ( log n )O(ilogri)O(ilogmi)O(logn)O(logn) waktu untuk memverifikasi.

Ada cara lain untuk membuktikan Proposisi 3: yaitu, perhatikan bahwa dalam , kita hanya perlu mempertimbangkan yang merupakan kekuatan utama: . Dalam hal itu, dua set pelanggaran yang perlu kita hitung juga memiliki ukuran yang merupakan kekuatan ; khususnya, jika mereka tidak sama, mereka berbeda dengan faktor setidaknya . Dengan demikian, cukup untuk menghitung ukuran dua set kira-kira . Ini dapat dilakukan dalam quasipolynomial menggunakan lemma coding Sipser. Dan seperti yang telah saya tunjukkan, dapat dihitung dalam quasipolynomial dengan kuadrat berulang.M m = p e p p A C 0 p o w A C 0()mm=peppAC0powAC0

Salah satu konsekuensi dari Proposisi 3 adalah bahwa jika masalah isomorfisma abelian ternyata tidak ada dalam , ini mungkin agak sulit untuk dibuktikan: khususnya, seseorang tidak dapat hanya mengurangi PARITY atau MAJORITY ke masalah, karena ini membutuhkan sirkuit dengan kedalaman terbatas ukuran-eksponensial , bukan quasipolynomial. Sekalipun kita berusaha mengurangi PARITY pada bit-bit ke masalah, tidak ada banyak ruang untuk parameter: secara khusus, PARITY dari super-polylogarithmically banyak bit tidak dapat dihitung oleh sirkuit-konstanta kedalaman-ukuran quasipolynomial, dan PARITY of Secara polilogaritma banyak bit sudah dapat dihitung dalam dengan membagi dan menaklukkan. m n A C 0AC0mnAC0

Referensi:

[1] Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner: Grafik isomorfisma bukan -dapat diturunkan ke grup isomorfismaAC0 , Transaksi ACM tentang Teori Komputasi 5 (2013), no. 4, artikel no. 13, doi: 10.1145 / 2540088 .

[2] David Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie: Tentang kerumitan beberapa masalah pada input kelompok sebagai tabel perkalian , Jurnal Ilmu Komputer dan Sistem 63 (2001), no. 2, hlm. 186–200, doi: 10.1006 / jcss.2001.1764 .

Emil Jeřábek
sumber
2
Terkait (dan sangat baru): arxiv.org/abs/1802.00659
Joshua Grochow