Kelompokkan isomorfisme untuk membuat grafik ismorfisme

Dalam membaca beberapa blog tentang kompleksitas komputasi (misalnya di sini ) saya berasimilasi gagasan bahwa memutuskan apakah dua kelompok isomorfik lebih mudah daripada menguji dua grafik untuk isomorfisme. Sebagai contoh, pada halaman lain dikatakan bahwa graf isomorfisme adalah masalah yang lebih umum daripada isomorfisme kelompok.

Karenanya saya mengajukan yang berikut ini

Diberikan grup dapat seseorang memberikan konstruksi grafik polinomial ukuran dalamsedemikian rupa sehingga untuk grup dan$G$$\Gamma(G)$$|G|$

$$\Gamma(G) \cong \Gamma(H) \iff G \cong H$$ $G$$H?$

Pengurangan dijelaskan dalam kertas klasik Miller.

Tidak secepat itu. Ada ambiguitas mengintai yang besar di sini:

Bagaimana Anda memasukkan grup Anda untuk perhitungan?

Tidak seperti grafik, kelompok dapat menjadi sarana input yang jauh berbeda dalam hal ukuran input dan kompleksitas yang dihasilkan. Versi yang dikutip dalam Miller adalah salah satu yang paling tidak alami dan misalnya Anda tidak akan menemukan bahwa dalam sistem aljabar komputer seperti GAP, Magma, atau Sage. Jadi, meskipun memiliki premis teoretis, akan terlalu jauh untuk menyebut penyelesaian masalah.

1. Generator dan Hubungan: Isomorfisme kelompok tidak dapat ditentukan (grafik isomorfisme dapat ditentukan).

Jika sejarah adalah pemenangnya, maka penyebutan pertama tentang masalah Isomorfisme Kelompok adalah oleh Max Dehn pada tahun 1905. Dia berasumsi bahwa kelompok akan menjadi masukan oleh generator dan hubungan. Adyan dan Rabin pada 1950-an membuktikan bahwa masalahnya tidak dapat diputus . Situasi ini terjadi bahkan jika kelompok itu sepele. Jadi ini bukan hanya masalah kardinalitas. Masalah utamanya adalah Anda dapat membuat grup tempat memutuskan apakah akan menyelesaikan masalah penulisan ulang yang bersifat non-primitif rekursif. Mirip dengan masalah jenis penghentian, itu tidak dapat dilakukan.$G$$G=1$

Untuk input grup oleh generator dan relasi: isomorfisme kelompok lebih sulit daripada isomorfisme grafik, pada kenyataannya tidak dapat diputuskan.

2. Input yang digunakan oleh sistem perangkat lunak: kelompok isomorfisma permutasi dan kelompok matriks setidaknya sekeras grafik isomorfisme (bukan sebaliknya).

Model masukan ini mengasumsikan kelompok dikodekan dalam beberapa cara alami, katakan sebagai permutasi pada himpunan terbatas, atau sebagai matriks atas cincin atau bidang. Ini adalah metode yang diperkenalkan oleh Cannon dan Neubuser dalam sistem aljabar komputer pertama pada 1960-an yang kemudian menjadi GAP dan Magma. Dalam model ini Anda dapat menanamkan masalah grafik isomorfisma ke dalam masalah kelompok isomorfisme. Lihat misalnya karya Heinekin-Liebeck. Sejak itu telah dilakukan dalam bentuk lain oleh orang lain seperti Sergeichuk. Gagasan kuncinya adalah untuk menanamkan matriks kedekatan dari sebuah grafik ke dalam hubungan -group.$p$

Untuk input grup untuk sistem perangkat lunak: isomorfisma grup paling tidak sekeras grafik isomorfisme.

3. Input Kompleksitas Teoretis: Untuk input grup kotak-hitam, isomorfisma grup tidak diketahui berada dalam NP atau ko-NP (grafik isomorfisma ada di keduanya).

Ini adalah model untuk grup yang disarankan oleh Babai-Szemeredi yang tidak mengasumsikan apa-apa tentang input kecuali bahwa ia dilengkapi dengan fungsi (biaya unit) untuk operasi grup, mengalikan, membalikkan, menguji kesetaraan, dan satu set generator. Dalam makalah mereka "Pada kompleksitas masalah kelompok matriks" mereka membahas masalah ini dan menyimpulkannya dalam . Masalah utamanya adalah Anda bahkan tidak dapat mendefinisikan sertifikat isomorfisme (sehingga tidak ada dalam NP) karena Anda hanya memiliki generator grup. Jadi untuk memberikan isomorfisme aktual tidak mungkin, dan secara eksponensial lebih besar dan dari generator saja Anda tidak dapat mengetahui apakah$\Sigma^2$$f:G\to H$$G$$H$$f$adalah homomorfisme yang valid. Minimal Anda tampaknya membutuhkan presentasi dari grup, dan itu tidak mudah diperoleh.

Untuk kelompok kotak hitam: kelompok isomorfisme setidaknya sekeras grafik isomorfisme.

4. Input tabel Cayley.

Suatu saat di tahun 1970-an Tarjan, Pultr-Hederlon, Miller dan yang lainnya mengamati bahwa input kelompok dengan seluruh tabel perkalian mereka juga dapat diperlakukan sebagai grafik. Dengan cara ini, isomorfisma kelompok berkurang menjadi grafik isomorfisme dalam waktu polinomial. Miller melangkah lebih jauh dengan mengamati bahwa banyak struktur kombinatorial melakukan hal yang sama, Steiner tiga kali lipat misalnya. Dia juga menunjukkan bahwa isomorfisma semigroup setara dengan grafik isomorfisme.

Baru-baru ini Babai membuktikan bahwa Grafik Isomorfisme berada dalam waktu polinomial semu dan pengurangan sekarang memperkirakan kompleksitas sekitar , yang tepatnya merupakan ikatan isomorfisma kelompok yang paling dikenal untuk kelompok yang diberikan oleh tabel Cayley. Meskipun tidak ada yang menunjukkan kedua masalah ini setara dengan waktu polinomial, penentuan waktu menunjukkan hubungan yang lebih dekat dari yang diharapkan.$n^{O(\log n)}$

Untuk tabel Cayley: isomorfisma kelompok direduksi menjadi grafik isomorfisme.

Input mana yang merupakan input grup "benar"? Nah kompleksitas Kolmogorov dari grup hingga dari order adalah yang kira-kira merupakan ukuran input dari metode 1-3 di atas. Metode input tersebut alami dan mudah dibuat, misalnya dengan menghitung permutasi pembuatan kubus Rubiks atau melihat pada pembuatan loop dari grup fundamental. Jadi masuk akal bahwa banyak teori dan praktik isomorfisme kelompok menggunakan model-model itu.$n$$O((\log n)^3)$

Namun sementara tidak ada sistem aljabar komputasi menggunakan tabel Cayley, dan sebagian besar ilmu komputer teoritis menggunakan struktur seperti kelompok permutasi, kelompok matriks, dan kelompok kotak hitam, masih ada pertahanan yang baik untuk perspektif tabel Cayley. Secara umum kompleksitas Kolmogorov struktur seperti semigroup adalah orde adalah - teorema Marshall Hall. Jadi Anda tidak bisa memasukkan semigroup lebih ringkas daripada dengan tabel perkalian. Oleh karena itu ketika Anda ingin membandingkan kompleksitas isomorfisma kelompok dengan struktur alami lainnya (kuasi-grup, loop, semi-grup, dll.) Masuk akal untuk menyetujui model input yang sama.$n$$O(n^2 \log n)$